数据结构习题 - 部分答案 - 全真模拟

云南财经大学信息学院

《数据结构》模拟试题题库

《数据结构》课程建设小组

模拟试题部分

一、单项选择题

1. 若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个

结点，则采用____（3）__________存储方式最节省运算时间。 （1）单链表 （2）双链表

(3) 容量足够大的顺序表 （4）带头结点的双循环链表

2. 若某线性表中最常用的操作是取第I 个元素的前驱元素，则采用____（3）

__________存储方式最节省运算时间。 （1）单链表 （2）双链表

(3)顺序表 （4）带头结点的双循环链表

3. 将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点

进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（______A____）。 A．98 B.99 C.50 D.48

4. 一个具有n个顶点的无向完全图的边数为（B）。

A．n(n+1)/2 B．n(n-1)/2 C． n(n-1) D．n(n+1)

5. 折半查找要求查找表中各元素的关键字值必须是____A_______排列。 A.递增或递减 B.递增 C.递减 D.无序 6. 栈操作的原则是 B 。

A. 先进先出 B.后进先出 C.只能进行插入 D. 只能进行删除

7. 设一个栈的输入序列为A，B，C，D，则借助一个栈所得的输出序列不可能是____

（4）___。

（1）A，B，C，D （2）D，C，B，A （3）A，C，D，B （4）D，A，B，C

8. 将下三角矩阵A[1..10，1..10]的所有非0 元素以行序为主序存放在首地址为2000

的存储区中，每个元素占有4个单元，则元素A[9，5]的首地址为（D） A．2340 B．2336 C．2164 D．2160 9. 串是______（4）_______。

（1） 不少于一个字母的序列 （2）任意个字母的序列 （3） 不少于一个字符的序列 （4）有限个字符的序列 10. 链表不具有的特点是______（1）______.

（1）可随机访问任一元素 （2）插入删除不需要移动元素 （3）不必事先估计存储空间 （4）所需空间与线性表长度成正比 11. 在有n个结点的哈夫曼树中，其结点总数为____（4）__________。

（1） （1） 不确定 （2）2n （3）2n+1 （4）2n-1 12. 任何一个无向连通图的最小生成树_____（2）______。

（1） 只有一棵 （2）有一棵或多棵 （3）一定有多棵 （4）可能不存在 13. 将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点

进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为____（1）______。 （1）98 （2）99 （3）50 （4）48

14. 将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点

进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为____2______。 （1）98 （2）99 （3）50 （4）48

15. 将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点

进行编号，根结点的编号为1，则编号为49的结点的双亲编号为____2______。 （1）23 （2）24 （3）25 （4）无法确定

16. 设计一个判别表达式中左右括号是否配对出现的算法，采用（B）数据结构最佳。 A．线性表的顺序存储结构 B．栈 C．队列 D．线性表的链式存储结构

17. 下列序列中，______（1）______ 是执行第一趟快速排序后得到的序列（排序的关

键字类型是字符串）。

（1）[da,ax,eb,de,bb]ff[ha,gc] (2)[cd,eb,ax,da]ff[ha,gc,bb] (3)[gc,ax,eb,cd,bb]ff[da,ha] (4)[ax,bb,cd,da]ff[eb,gc,ha]

18. 用n个键值构造一棵二叉排序树，最低高度为___（4）_________。 （1）n/2 (2)n1/2 (3)NLOG2N

(4)[LOG2N]+1

19. 折半查找要求查找表中各元素的关键字值必须是___1________排列。 （1） 递增或递减 （2）递增 （3）递减 （4）无序

20. 对于关键字值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，

必须从关键字值为_____（3）____的结点开始。 （1）100 （2）12 （3）60 （4）15

21. 快速排序的记录移动次数（C）比较次数，其总执行时间为0（NLOG2N） A．大于 B．大于等于 C．小于等于 D．小于 22. 3个结点可构成（D）个不同形态的二叉树。 A．2 B．3 C．4 D．5

23. 对有n个记录的有序表采用二分查找，其平均查找长度的量级为（A） A．O（LOG2N） B．O（NLOG2N） C．O（N） D．O（N2）

24. 对有n个记录的表按记录键值有序的顺序建立二叉排序树，在这种情况下，其平均

查找长度的量级为（C）

A．O（LOG2N） B．O（NLOG2N） C．O（N） D．O（N2）

25. 设矩阵A[1..8,1..8]是一对称矩阵，若每个矩阵元素占3个单元，将其上三角部分按

行序为主序存放在数组B中，B的首址为1000，则矩阵元素A[6，7]的地址为（B） A．1031 B．1093 C．1096 D．1032

26. 链表适用于顺序查找，但在链表中进行（D）操作的效率比在顺序存储结构中进行

同样操作的效率高。

A．顺序查找 B．二分法查找 C．快速查找 D．插入 27. 散列法中的冲突指的是（C）。

A．两个元素具有相同的序号 B．两个元素的键值不同，而其它属性相同 C．不同键值的元素对应于相同的存储地址 D．数据元素过多 28. 如果以链表作为栈的存储结构，则退栈操作时（C）

A．必须判断栈是否满 B．对栈不作任何判断 C．必须判断栈是否空 D．判断栈元素的类型

29. 设数组A[0..M]作为循环队列SQ的存储空间，front 为队头指针，rear为对尾指针，

则执行出队操作的语句为（D）

A．front=front+1 B．front=(front+1)%m C．rear=rear+1 D．rear=(rear+1)%m 30. 深度为6的二叉树至多有（D）个结点 A．64 B．32 C．31 D．63

31. 设高度为k的二叉树上只有度为0和2的结点，则此类二叉树中所含的结点数至少

为（C）

A．K+1 B．2K C．2K-1 D．2K+1 32. 堆的存储表示（A）

A．顺序存储 B.静态链接存储 C.动态链接存储 D.不一定 33. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用( A )

遍历方法最合适。

A．前序 B．中序 C．后序 D．按层次

34. 利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉

排序树以后，查找元素35要进行( A )元素间的比较。 A．4次 B．5次 C. 7次 D．10次

35. 下面给出的四种排序法中( D )排序法是不稳定性排序法。 A．插入 B．冒泡 C．二路归并 D．堆积

36. 下面 B 方法可以判断出一个有向图中是否有环（回路）？ A.深度优先遍历 B.拓朴排序 C.求最短路径 D.求关键路径

37. .若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( D ) A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构

38. 在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为

( A )

A.n-i+1 B.n-i C.i D.i-1

39. .对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( C ) A.顺序表 B.用头指针表示的单循环链表 C.用尾指针表示的单循环链表 D.单链表

40. .为查找某一特定单词在文本中出现的位置，可应用的串运算是( D ) A.插入 B.删除 C.串联接 D.子串定位

41. 已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数

Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到( A )

A.P=″SCIENCE″ B.P=″STUDY″ C.S=″SCIENCE″ D.S=″STUDY″

42. 三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，

且数组中第一个元素的存储地址为120，则元素A[3][4][5]的存储地址为(B ) A.356 B.358 C.360 D.362 43. 如右图所示广义表是一种( C )

A.线性表 B.纯表 C.结点共享表 D.递归表

44. 下列陈述中正确的是( D )

A.二叉树是度为2的有序树

B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为2的结点

D.二叉树中最多只有两棵子树，并且有左右之分

45. n个顶点的有向完全图中含有向边的数目最多为( D )

A.n-1 B.n C.n(n-1)/2 D.n(n-1)

46. 已知一个有向图如右所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS

序列为( A )

A.a d b e f c B.a d c e f b C.a d c b f e D.a d e f bc

47. .在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是( C ) A.快速排序 B.堆排序 C.归并排序 D.基数排序 48. 不可能生成右图所示二叉排序树的关键字序列是( A )

A.4 5 3 1 2 B.4 2 5 3 1 C.4 5 2 1 3 D.4 2 3 1 5

49. ALV树是一种平衡的二叉排序树，树中任一结点的( B )

A.左、右子树的高度均相同 B.左、右子树高度差的绝对值不超过1 C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度 50. 在VSAM文件的控制区间中，记录的存储方式为( ) A.无序顺序 B.有序顺序 C.无序链接 D.有序链接

二、判断题(判断下列各题是否正确，若正确在括号内打“√”，错误的打； 1．如果两个串含有相同的字符，则这两个串相等。（N）

2．数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。( N)， 3．在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块元素个数有关。（Y）

4．在顺序表中取出第i个元素所花费的时间与i成正比。（N） 5．在栈满情况下不能作进栈运算，否则产生“上溢”。（Y）

6．二路归并排序的核心操作是将两个有序序列归并为一个有序序列，(Y)

7．对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点。（N）

8．二叉排序树或是一棵空二叉树，或是具有下列性质的二叉树；若它的左子树非空，则根

结点的值大于其左孩子的值；若它的右子树非空，则根结点的值小于其右孩子的值。（N） 9．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的(N)。

10．一个有向图的邻接表和逆邻接表中表结点的个数一定相等（Y） ①（101，88，46，70，34，39，45，58，66，10）是堆（Y）； ② 将一棵树转换成二叉树后，根结点没有左子树（N）；

③ 用二叉树的前序遍历和中序遍历可以导出树的后序遍历（Y）；

④ 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同(N)；

⑤ 哈夫曼树是带权路径长度最短的二叉树，路径上权值较大的结点离很较近（Y）。 11、表示一个有1000个顶点、1000条边的有向图的邻接矩阵有1000000个矩阵元素，是否稀疏矩阵 是

12.（ N）串长度是指串中不同字符的个数。

13.（ N）数组可以看成是线性结构的一种推广，因此可以对它进行插入、删除等运算。 14.（ Y）在顺序表中取出第i个元素所花费的时间与i成正比。 15. ( Y)在栈满的情况下不能作进栈的运算，否则产生“上溢”。

16.（ Y二路归并排序的核心操作是将两个有序序列归并为一个有序序列。

17.（ N ）对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。

18.（ Y）一个有向图的邻接表和逆邻接表中的结点个数一定相等。

19（ Y）在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。

12（ N）叉排序树或者是一棵空树，或者 是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值；若它的右子树非空，则根结点的值小于其右孩子的值。 21（ N）执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。

三、填空题

1. 在带有头结点的单链表L中，第一个元素结点的指针是___L->next________。

2. 在双循环链表中，在指针p所指结点前插入指针s所指的结点，需执行下列语句： s->next=p; s->prior=p->prior; p->prior=s; _s->prior->next_______________=s;

3. 设s[1..maxsize]为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件是___top==0__________，栈为满的条件是________top==maxsize_____________。 4. 具有100个结点的完全二叉树的深度为______7__________________。

5. 有向图G用邻接矩阵A[1..n,1..n]存储，其第i行的所有元素之和等于顶点i的____出度_______________。

6．r指向单链表的最后一个结点，要在最后一个结点之后插入e所指的结点，需执行的三条语句是r->next=s; r=s；r—>next=NULL。

7在单链表中，指针p所指结点为最后一个结点的条件是p->next==null

8设一个链栈的栈顶指针是ls，栈中结点格式为info;link;栈空的条件是 ls==null。如果栈不为空，则退栈操作为p=ls； ls=ls->link；free(p)。

9已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有12个叶子结点。

10．图有三种常用的存储结构，即孩子链表法，孩子兄弟链表法和 双亲表示法。

11．n个顶点的连通图的生成树有n-1条边。

12．一个有向图G中若有弧、< vj,vk >和< vi,vk >，则在图G的拓扑序列中，顶点vi,vj vk的相对位置为i,j,k

13．设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序 方法对其进行排序(按递增顺序)：冒泡最省时间，快速最费时间。

14。下面是将键值为x的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。 typedef struct pnode }int key；

struct node *left，*right； }

void searchinsert(int x;pnode t) /*t为二叉排序树根结点的指针*/ {if (t==null)

{p=malloc(size); p->key=x;p->left=null; p->right=null;t=p; } else

if (xkey) searchinsert(x,t->left) else searchinsert(x,t->right) } 15．线性表的循环链表的主要优点是从表中任一结点出发都能访问到所有的结点。而使用双向链表，可根据需要在前后两个方向上方便地进行查找。 16．在带有头结点的单链表L中，则需执行下列三条语句：u=L->next ；L—>next=u->next；free(u); 17．有一个长度为20的有序表采用二分查找方法进行查找，共有4 个元素的查找长度为3。 18．采用冒泡排序对有n个记录的表A按键值递增排序；若L的初始状态是按键值递增，则排序过程中记录的比较次数为n-1。若A初始状态为递减排列，则记录的交换次数为n(n-1)/2 19.在无头结点的双链表中，指针p所指结点是第一结点的条件是p->prior==null.

20．G为无向图，如果从q的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是连通图。

21．如果一个有向图中没有环，则该图的全部结点可以排成一个拓扑序列。 22．深度为8(根的层次号为1)的满二叉树有8 个叶子结点。

23．将一棵有100个结点的完全二叉树按层编号，则编号为49的结Ⅸ，其双亲PARENT(X) 的编号为 24 。

24．设有一个链队，结点结构为data;next；front为队头指针，rear为队尾指针，当执行入队操作时需执行下列语句：malloc(p);p->data=x;p->next=null;rear->next=p;rear=p; 25.在散列法中，元素个数 越多，发生冲突的可能性越大。

26．在带有头结点的单链表L中，第一个元素结点的指针是 L->next。 27．在顺序文件中，存取第i个记录，必须先存取 第I-1号元素。

28．设s[1..maxsize]为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件是 top==0，栈为满的条件是 top==maxsize

29．具有64个结点的完全二叉树的深度为 7

30．有向图G用邻接矩阵A[1..N,1..N]存储，其第I列的所有元素之和等于顶点I的入度。

31．在双循环链表中，若要在指针P所指结点前插人指针S所指的结点，则需执行下列语句 s->next=p;s->prior=p->prior;p->prior=s;s->prior->next=p;

32．对于下图所示二叉树；按前序遍历所得到的结点序列A，B，D，E，H，C，F．

33．分别采用堆排序、快速排序、冒泡排序和归并排序算法对初始状态为递增序列的表按递增顺序排序，最省时间的是冒泡排序 ，最费时间的是快速算法

34. 对于下面的二叉树，按中序遍历所得到的结点序列为_______________。 35. 对下图所示的网，执行prim算法可得到最小生成树，试在下表的空白处填上适当的内容，以说明该算法的执行过程。

1

1 5

5 3

4 2

2

顶点 1 4

3 （2，3） 4 （2，3） 4 4 （U，V） （2，1） 代价 ∞ （U，V） 代价 （U，V） （3，1） 1 代价 U {2} V {1，3，4} {1，3} {1} （2，4） 2 {2，4} {2，4，3} （U，V） {2，4，3，1} 代价

36、设广义表L＝(（），（）) 则head(L)是 () ；tail(L)是 (())；L的长度是 2 ；深度是 2

37、在n个记录的有序顺序表中进行折半查找，最大的比较次数是logn 。

在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是_S->NEXT->NEXT=P->NEXT_和_P->NEXT=S__。

38．串S=″I am a worker″的长度是_14_______。

假设一个10阶的下三角矩阵A按列优顺序压缩存储在一维数组C中，则C数组的大小应为__55____。

39．在n个结点的线索二叉链表中，有___n+1_个线索指针。

40．对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为_48,44,52,63,80,91___。

二、应用题

1． 已知二叉树的后跟序列和中根序列如下，构造出该二叉树。

后根序列：ABCDEFG 中根序列：ACBGEDF

2． 有一组关键码序列{8，9，5，3，7，2，1}，分别采用冒泡排序、快速排序、直接选择

排序、直接插入排序、二路归并排序方法由小到大进行排序，在下面的选项中请选择各种排序第一趟排序的结果。 冒泡排序：E 快速排序：A 直接选择排序：B 直接插入排序：C 二路归并：F

A．{1，2，5，3，7，8，9} B．{1，9，5，3，7，2，8} C．{9，8，5，3，7，2，1} D．{9，5，3，7，2，1，8} E．{8，5，3，7，2，1，9} F．{8，9，3，5，2，7，1} 3． 设图G=（V，E），V={1，2，3，4，5，6}，E={<1，2>，<1，3>，<2，5>，<3，6>，

<6，5>，<5，4>，<6，4>}，请写出图G中顶点的所有拓扑序列。 4． 设图G=（V，E），V={1，2，3，4，5，6}，E={<1，2>，<1，3>，<2，5>，<3，6>，

<6，5>，<5，4>，<6，4>}，请画出其邻接表，并说明每个顶点的入度和出度。 5． 对如下所示的二叉树，画出其顺序存储结构。

6． 已知图G的邻接表如图所示，画出图G的所有连通分量。

现有5个结点（A，B，C，D，E），它们的权值分别为{5，10，12，15，30}，在下面

的选项中选择一个编号，说明这5个结点的哈夫曼编码。（2）

（1） （2） （3） （4）

A：1，B：001，C：010，D：011，E：000 A：000，B：001，C：010，D：011，E：1 A：001，B：011，C：010，D：000，E：1 A：000，B：1，C：010，D：011，E： 001

7． 已知一表为{23，45，24，6，57，45，35}，按表中顺序依次插入初始为空的二叉排序

树，要求画出建立的二叉排序树。

设有序序列30,18,3,61,14,49，请按该序列构成一棵二叉排序树，并求其查找成功时的平均查找长度。 答：二叉排序树: (3分)

=2.5 (2分)

平均查找长度= (1+2×2+3×2+4) * 1/6

8． 对如下所示的交通网，顶点表示城市，边表示连接城市间的公路，边上的权表示修路的

代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出所有可能的方案。 9． 设有n个元素的有序表为A，K为一个给定的值，填空完成二分查找算法： binsrch(a,n,k) int a[],k;

{ int low,hig,mid; low=0; hig=n;

while(low<=hig)

{ mid=(low+hig)/2; if(k

if(a[mid]==k)

printf(\ else

printf(\}

10．已知带权图的邻接矩阵表示和邻接表表示的形式说明分别如下：

#define MaxNum 50//图的最大顶点数

#define INFINITY INT_MAX //INT_MAX为最大整数，表示∞

typedef struct{

char vexs[MaxNum];//字符类型的顶点表

int edges[MaxNum][MaxMum];//权值为整型的邻接矩阵

int n,e;//图中当前的顶点数和边数

}MGraph;//邻接矩阵结构描述

typedef struct node {

int adjvex;//邻接点域

int weight;//边的权值

struct node *next;//链指针域

} EdgeNode;//边表结点结构描述

typedef struct {

char vertex;//顶点域

EdgeNode * firstedge;//边表头指针

} VertexNode ;//顶点表结点结构描述

typedef struct {

VertexNode adjlist[MaxNum];//邻接表

int n,e;//图中当前的顶点数和边数

} ALGraph;//邻接表结构描述

下列算法是根据一个带权图的邻接矩阵存储结构G1建立该图的邻接表存储结构G2，请填入合适的内容，使其成为一个完整的算法。

void convertM(MGraph *G1,ALGraph *G2) {

int i,j;

EdgeNode * p;

G2->n=G1->n;

G2->e=G1->e;

for(i=0;in;i++)

{

G2->adjlist[i].vertex=G1->vexs[i];

G2->adjlist[i].firstedge= (1) ; }

for (i=0;in;i++)

for (j=0;jn;j++)

if(G1->edges[i][j]

{

p=(EdgeNode *) malloc(sizeof(EdgeNode));

p->weight= (2) ;

p->adjvex=j;

p->next=G2->adjlist[i].firstedge;

(3) ;

} }

(1) NULL

(2) G1->edges[i][j]

(3) G2->adjlist[i].firstedge=p

11.阅读下列算法，并回答下列问题：

(1)该算法采用何种策略进行排序? 插入排序

(2)算法中R[n+1]的作用是什么? 监视哨

Typedef struct {

KeyType key;

infoType otherinfo;

} nodeType;

typedef nodeType SqList［MAXLEN］;

void sort(SqList R,int n) {

//n小于MAXLEN-1

int k;i;

for(k=n-1;k>=1;k--)

if(R[k].key>R[k+1].key)

{

R[n+1]=R[k];

for(i=k+1;R[i].key

R[i-1]=R[i];

R[i-1]=R[n+1];

} }

12．设某二叉树以二叉链表为存储结构，请写出求其高度的递归算法。 答：void BTdepth (BinTree BT,int h) {

int hr, h1;

if(BT==null) h=0; (1分) else {

BTdepth (BT→lchild,h1); 2分 BTdepth (BT→rchild,hr);

if(h1>=hr)h=h1+1; 2分 else h=hr+1

} }

四、算法填空和分析

1、ListInsert_L(LinkList L, int pos, ElemType e)

//在带头结点的单链表L中第pos个数据元素之前插入数据元素e Status ListInsert_L(LinkList L, int pos, ElemType e) {

p = L; j = 0;

while (p && j < pos-1)

{ p = p->next; ++j; } // 寻找第pos-1个结点 if (!p || j > pos-1)

return ERROR; // pos小于1或者大于表长

s = (LinkList) malloc ( sizeof (LNode)); // 生成新结点 s->data = e; s->next = p->next; // 插入L中 p->next = s; return OK; }

2、void Merge (Elem SR[], Elem TR[], int i, int m, int n) {

// 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] for (j=m+1, k=i; i<=m && j<=n; ++k) { // 将SR中记录由小到大地并入TR

if (SR[i].key<=SR[j].key) TR[k] = SR[i++]; else TR[k] = SR[j++]; }

if (i<=m) TR[k..n] = SR[i..m]; // 将剩余的SR[i..m]复制到TR if (j<=n) TR[k..n] = SR[j..n]; // 将剩余的SR[j..n]复制到TR } // Merge 3、

int Partition (Elem R[], int low, int high)

{// 交换记录子序列R[low..high]中的记录，使枢轴记录到位，并返回//其所在位

置，此时，在它之前（后）的记录均不大（小）于它 R[0] = R[low];// 用子表的第一个记录作枢轴记录 pivotkey = R[low].key; // 枢轴记录关键字 while (low

// 从表的两端交替地向中间扫描

while(low=pivotkey)

--high;

R[low] = R[high];// 将比枢轴记录小的记录移到低端 while (low

}

R[low] = R[0]; // 枢轴记录到位 return low; // 返回枢轴位置 } // Partition

4、折半查找算法：

int binsrch(JD r[],int n,int k) { int low,high,mid,found; low=1; high=n; found=0;

while((low<=high)&&(found==0)) { mid=(low+high)/2;

if(k>r[mid].key) low=mid+1; else if(k==r[mid].key) found=1; else high=mid-1; }

if(found==1) return(mid); else

return(0); }

5、设有一个表头为head的单链表。通过遍历一趟链表，将链表中所有结点按逆序链接。

Typedef struct node {int data;

struct node *next; }pointer;

Void invert(pointer head) {p=NULL;

while (head!=NULL) {u=head;

head=head->next; u->next= p ; p=u; }

had=p; }

五、编写算法：

1、设某单链表L的结点结构如下，单链表L用于存放某人的电话薄，现在由于电话号码从7位升为8位（加60000000），请用C语言编写算法，实现电话薄中所有电话号码从7位升为8位。 Typedef struct node {

char name[9];//姓名

long data;//电话号码 struct node *next; }pointer;

int length(pointer L) {

p=L;

while(p!=NULL)

{ p->data= p->data+60000000;p=p->next;} }

2、设二叉树采用二叉链表表示，编写算法，将二叉树中所有结点的左右子树相互交换。

void Bitree_Revolute(Bitree T)//交换所有结点的左右子树 {

T->lchild<->T->rchild; //交换左右子树 if(T->lchild) Bitree_Revolute(T->lchild); if(T->rchild) Bitree_Revolute(T->rchild); //左右子树再分别交换各自的左右子树 }

设计题：

1． 设某单链表L的结点结构为data,next,试画出该链表的结构图，并用类C语言编写算法，

判断该链表的元素是否是递增的。

2． 设某单链表L的结点结构为data,next,试画出该链表的结构图，并用类C语言编写算法，

统计该链表的长度。

3． 设一棵二叉树以二叉链表作为存储结构，结点结构为lch,data,rch，其中data域中存放一

个字符，设计一个算法按前根遍历顺序打印出data域为数字的字符。

4． 设BT为二叉排序树，t指向根结点，每个结点的结构为lch,key,rch，试用类C语言写出

算法，用来输出二叉排序树中最小的键值。

5． 设一棵二叉树以二叉链表为存储结构，结点结构为lch,data,rch，设计一个算法求此二叉

树上度为2的结点数。

6． 设一个环上有若干个整数，若采用单循环链表L存储该环，L的存储结构为：data,next，

试画出链表L的结构图，并编写算法判断环上任意两个相邻的键值之差的绝对值是否不超过2。

7.假设二叉树T采用如下定义的存储结构： typedef struct node { DataType data;

struct node *lchild,*rchild; }PBinTree;

其中，结点的lchild域和rchild域已分别填有指向其左、右孩子结点的指针。请编写一个递归算法，将该存储结构中各结点的lchild和rchild域的值进行交换。

2001年10月数据结构试题及答案

一、 单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

1．算法指的是（ ）

A．计算机程序 B．解决问题的计算方法 C．排序算法 D．解决问题的有限运算序列 2．线性表采用链式存储时，结点的存储地址（ ） A．必须是不连续的 B．连续与否均可 C．必须是连续的

D．和头结点的存储地址相连续

3．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ）

A．O（1） B．O（n） C．O（m） D．O（m+n） 4．由两个栈共享一个向量空间的好处是：（ ） A．减少存取时间，降低下溢发生的机率 B．节省存储空间，降低上溢发生的机率 C．减少存取时间，降低上溢发生的机率 D．节省存储空间，降低下溢发生的机率

5．设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ）

A．front=front+1 B．front=(front+1)%(m-1) C．front=(front-1)%m D．front=(front+1)%m 6．如下陈述中正确的是（ ）

A．串是一种特殊的线性表 B．串的长度必须大于零 C．串中元素只能是字母 D．空串就是空白串

7．若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（ ）

A．O（ ） B．O（n） C．O（n2） D．O（n3） 8．一个非空广义表的表头（ ）

A．不可能是子表 B．只能是子表

C．只能是原子 D．可以是子表或原子 9．假设以带行表的三元组表表示稀疏矩阵，则和下列行表

0 2 3 3 5

对应的稀疏矩阵是（ ）

10．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( )

A．4 B．5 C．6 D．7

11．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( ) A．e B．2e C．n2－e D．n2－2e

12．假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是( )

A．O(n) B．O(e) C．O(n+e) D．O(n*e)

13．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：

20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（ ）

A．选择排序 B．希尔排序 C．归并排序 D．快速排序 14．适于对动态查找表进行高效率查找的组织结构是（ ）

A．有序表 B．分块有序表 C．三叉排序树 D．线性链表 15．不定长文件是指（ ）

A．文件的长度不固定 B．记录的长度不固定 C．字段的长度不固定 D．关键字项的长度不固定

第二部分 非选择题（共70分）

二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）不写解答过程，将正确的答案写在每小题的空格内。错填或不填均无分。

16．数据的逻辑结构是从逻辑关系上描述数据，它与数据的 无关，是独立于计算机的。

17．在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head= 。 18．栈顶的位置是随着 操作而变化的。

19．在串S=“structure”中，以t为首字符的子串有 个。

20．假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中，其中B�存储矩阵中第1个元素a1,1,则B中存放的元素是 。 21．已知一棵完全二叉树中共有768结点，则该树中共有 个叶子结点。 22．已知一个图的广度优先生成树如右图所示，则与此相 应的广度优先遍历序列为 。

23．在单链表上难以实现的排序方法有 和 。

24．在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进

行的关键字比较次数为 。 25．多重表文件和倒排文件都归属于 文件。 三、解答题（本大题共4小题，每小题5分，共20分） 26．画出下列广义表的共享结构图形表示 P=（（（z）,(x,y)）,((x,y),x),(z)） 27．请画出与下列二叉树对应的森林。

28．已知一个无向图的顶点集为{a, b, c, d, e} ,其邻接矩阵如下所示

(1)画出该图的图形；

（2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。

29．已知一个散列表如下图所示： 35 20 33 48 59

0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函数为h(key)=key, 处理冲突的方法为双重散列法，探查序列为： hi=(h(key)+ *h1(key))%m =0,1,?，m－1 其中

h1(key)=key+1 回答下列问题：

（1）对表中关键字35，20，33和48进行查找时，所需进行的比较次数各为多少？

（2）该散列表在等概率查找时查找成功的平均查找长度为多少？ 四、算法阅读题（本大题共4小题，每小题5分，共20分） 30．下列算法的功能是比较两个链串的大小，其返回值为： comstr(s1,s2)= 请在空白处填入适当的内容。

int comstr(LinkString s1,LinkString s2) {//s1和s2为两个链串的头指针 while(s1&&s2){

if(s1－>datedate)return－1； if(s1－>date>s2－>date)return1； ① ； ② ； }

if( ③ )return－1； if( ④ )return1； ⑤ ； }

① ② ③ ④ ⑤

31．阅读下面的算法

LinkList mynote(LinkList L)

{//L是不带头结点的单链表的头指针 if(L&&L->next){

q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL； }

return L； }

请回答下列问题：

（1）说明语句S1的功能；

（2）说明语句组S2的功能；

（3）设链表表示的线性表为（a1,a2, ?,an）,写出算法执行后的返回值所表示的线性表。

32．假设两个队列共享一个循环向量空间（参见右下图）， 其类型Queue2定义如下： typedef struct{

DateType data[MaxSize]； int front??,rear??； }Queue2；

对于i=0或1，front[i]和rear[i]分别为第i个队列的头指针和尾指针。请对以下算法填空，实现第i个队列的入队操作。

int EnQueue (Queue2*Q,int i,DateType x)

{//若第 i个队列不满，则元素x入队列，并返回1；否则返回0 if(i<0||i>1)return 0；

if(Q－>rear[i]==Q－>front[ ① ]return0； Q－>data[ ② ]=x； Q－>rear[i]=[ ③ ]; return1； } ① ② ③

33．已知二叉树的存储结构为二叉链表，阅读下面算法。 typedef struct node { DateType data； Struct node * next； }ListNode；

var

X,Y,Z:Integer;

Begin

If N=1 Then

Begin

m:=1;

p:=a[1]

End Else

Begin

X:=N;

N:=N-1;

Y:=P(A,Z,N);

N:=X;

If A[N]>=Y Then

Begin

M:=N;

P:=A[N]

End Else

Begin

M:=Z;

P:=Y

End

End

End;

Begin

Readln(N);

For I:=1 To N Do Read(A[I]);

Readln;

L:=N;

For I:=1 To L Do

Begin

K=P9A,J,N);

A[J]:=A[N];

A[N]:=K;

N:=N-1

End;

For I;=1 To L Do Write(A[I]:3);

Writeln;

End;

输入数据为：

8

6 1 8 4 3 5 2 7

9 （10分）

已知二叉树用下面的顺序结构存储，写出中序遍历该二叉树的算法。

Type

Array [1..maxn] of

Record

Data:Char; //存结点值

Lc,Rc:Integer //左、右孩子下标，0表示无左、右孩子

如树T=A（B（D，E），C（#，F（H，I）））存储如表1所示：

表1 树T的存储

1 2 3 4 5 6 7 8 9

A 2 3 B 4 5 C 0 6 D 0 0 E 0 7 F 8 9 G 0 0 H 0 0 I 0 0

10 （10分）

试写出以带头结点单链表为存储结构实现简单选择排序的算法。

东北大学2000硕士入学数据结构试题

1 （20分）

简要回答下列问题 ① （3分）

内存中一片连续空间（不妨假设地址从1到m），提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。

②（5分）

假设字符a,b,c,d,e,f的使用频度分别是0.07,0.09,0.12,0.22,0.23,0.27，写出a,b,c,d,e,f的Huffman（哈夫曼）编码。

③（4分）

一棵共有n个结点的树，其中所有分枝结点的度均为k，求该树中叶子结点的子数。

④（4分）

图1表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。

图1 题1.4图

⑤（4分）

在起泡（汽泡）排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，试举例说明之。快速排序过程中有没有这种现象？

2 （15分）

设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法：

① 找出最小值结点，且打印该数值；

② 若该数值是奇数，则将其与直接后继结点的数值交换；

③若该数值是偶数，则将其直接后继结点删除；

3 （14分）

解答下列问题：

① (4分）

将算术表达式 ((a+b)+c*(d+e)+f)*(g+h) 转化为二叉树；

② (10分）

假设一个仅包含二元运算符的算术表达式以二叉链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。

4（21）

解答下列问题：

① （5分）

画出有向图的十字链表存储结构中头结点和表结点的结点结构。

② (4分）

下面哪一个方法可以判断出一个有向图中是否有环（回路）？

(1)深度优先遍历 (2)拓朴排序 (3)求最短路径 (4)求关键路径

③(12分）

假设一个有向图g已经以十字链表形式存储在内中，试写一个判断该有向图中是否有环（回路）的算法。

5（15分）

写出删除二叉排序树bt中值为x的结点的算法（二叉排序树以二叉链表形式存储，删除后仍然保持二叉排序性质）。

6（15分）

设有大小不等的n个数据组（n个数据组中数据的总数为m），顺序存放在空间区D内，每个数据占一个存储单元，数据组的首地址由数组s给出（如下图所示），试编写将新数据x插入到第i个数据组的末尾且属于第i个数据组的算法，插入后，空间区D和数组S的相互关系仍保持正确。

图2 题6图

02年北京文考“数据结构”试题

一、判断题 (每小题1分，共15分)

1.程序就是算法，但算法不一定是程序。( )

2.线性表只能采用顺序存储结构或者链式存储结构。( )

3.线性表的链式存储结构是通过指针来间接反映数据元素之间逻辑关系的。( ) 4.除插入和删除操作外，数组的主要操作还有存取、修改、检索和排序等。( ) 5.稀疏矩阵中0元素的分布有规律，因此可以采用三元组方法进行压缩存储。( ) 6.不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。( ) 7.确定串Ｔ在串Ｓ中首次出现的位置的操作称为串的模式匹配。( ) 8.深度为h的非空二叉树的第i层最多有2i-1 个结点。( ) 9.满二叉树就是完全二叉树。( )

10.已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。( ) 11.非空二叉排序树的任意一棵子树也是二叉排序树。( )

12.对一棵二叉排序树进行前序遍历一定可以得到一个按值有序的序列。( ) 13.若有向图G=(V,E)的拓扑序列不唯一，则图中必须有两条弧和。( )

14.散列表的查找效率主要取决于所选择的散列函数与处理冲突的方法。( ) 15.序列初始为逆序时，泡排序法所进行的元素之间的比较次数最多。( ) 二、单项选择题 (每小题2分，共20分) 1.算法分析的目的是( )

A.研究算法的输入与输出之间的关系 B.找出数据结构的合理性 C.分析算法的效率以求改进算法 D.分析算法的可读性与可移植性

2. 在由list所指的非空线性链表中删除由p指的链结点的下一个链结点的过程是依次执行q←link(p),____________,call RET(q)。( ) A.link(p)←q B.link(q)←p

C.link(q)←link(p) D.link(p)←link(q)

3.依次在初始为空的队列中插入元素为a,b,c,d以后，紧接着作了两次删除操作，此时的队头元素是( ) A.a B.b C.c D.d

4.若某堆栈的输入序列为 1，2，3，?，n-1，n，输出序列的第1个元素为n，则第个输出元素为( ) A.n-i+1 B.n-1

C.i D.哪个元素无所谓

5.设计递归问题的非递归算法一般需要用到__________机制。( ) A.数组 B.堆栈 C.队列 D.二叉树

6.已知非空二叉树采用顺序存储结构，树中结点的数据信息依次存放在一个一维数组中，即 ABC□DEF□□G□□H□□ 该二叉树的中序列遍历序列为( ) A.G,D,B,A,F,H.C,E B.G,B,D,A,F,H,C,E C.B,D,G,A,F,H,C,E D.B,G,D,A,F,H,C,E

7.在一棵度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有2个，那么，该树有__________个叶结点。( ) A.4 B.5 C.6 D.7

8.已知有向图G=，其中V＝{v1,v2,v3,v4,v5,v6},E＝{,，，，，，，}，G的拓扑序列是______。( )

A.v3,v1,v4,v5,v2,v6 B.v3,v4,v1,v5,v2,v6 C.v1,v3,v4,v5,v2,v6 D.v1,v4,v3,v5,v2,v6

9.在初始为空的散列表中依次插入关键字序列(MON,TUE,WED,THU,FRI,SAT,SUN),散列函数为H(k)=i MOD 7，其中，i为关键字k的第一个字母在英文字母表中的序号，地址值域为 [0:6] ，采用线性再散列法处理冲突。插入后的散列表应该如__________ 所示。( ) A. 0 1 2 3 4 5 6

THU TUE WED FRI SUN SAT MON B. 0 1 2 3 4 5 6

TUE THU WED FRI SUN SAT MON C. 0 1 2 3 4 5 6

TUE THU WED FRI SAT SUN MON D. 0 1 2 3 4 5 6

TUE THU WED SUN SAT FRI MON

10. 对数据元素序列(49，72，68，13，38，50，97，27)进行排序，前三趟排序结束时的结果依次为：第一趟：13，72，68，49，50，97，27；第二趟：13，27，68，49，38，50，97，72；第三趟：13，27，38，49，68，50，97，72；该排序采用的方法是( )

A.插入排序法 B.选择排序法 C.泡排序法 D.堆积排序法

三、填空题 (每小题2分，共20分)

1.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新的数据元素前，需要先依次移动_________个数据元素。

2.在非空双向循环链表中由q所指的那个链结点后插入一个由p指的链结点的动作对应的语句依次为：llink(p)←q，rlink(p)←rlink(q)，rlink(q)←p,______________。(空白处为一条赋值语句)

3.已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为LOC(a1)，那么，LOC(ai)=________________。 4.具有2000个结点的二叉树，其深度至少为_________。

5.具有n0个叶结点的哈夫曼树 (Huffman) 的分支总数为_________。 6.若连通图的顶点个数为n，则该图的生成树的边数为_________。

7.在序列(2，5，8，11，15，16，22，24，27，35，40)中采用折半查找(二分查找)方法查找元素24，需要进行_________次元素之间的比较。

8.索引文件中的索引表是_________提供的，并且索引表的表项按_________有序列排列。

9.对具有n个元素的任意序列采用插入排序法进行排序，整个排序过程中要进行_________次元素之间的比较。

10.插入排序法、选择排序法、拓扑排序法与归并排序法中，_________不是内排序方法。

四、问题求解题 (每小题10分，共20分)

1.已知一带权连通图采用邻接矩阵存储方法，并且邻接矩阵采用三元组表表示，其中，第一个三元组 (5，5，16)分别表示邻接矩阵的行数、列数字与非零元素的个数，从第二个三元组开始，依次按行序为主序的次序分别给出16个非零元素，它们依次为(1，2，7)，(1，3，6)，(1，4，9)，(2，1，7)，(2，3，8)，(2，4，4)，(2，5，4)，(3，1，6)，(3，2，8)，(3，4，6)，(4，1，9)，(4，2，4)，(4，3，6)，(4，5，2)，(5，2，4)，(5，4，2)；请分别画出该带权连通图的两棵最小生成树。

2.已知散列范围为[0：9]，散列函数为H(key)=key MOD 9，处理冲突的方法为链地址法，请画出依次插入关键字8,10,14,19,21,23,28,32以后的哈希表。 五、算法题 (本题共25分)

1. (10分)下面的算法将一维数组A[1:n]中所有奇数移到数组的左边，所有偶数字移到数组的右边。请在算法的空白处填入适当内容，使之能够正常工作。(提示：用 x MOD y表示求x除以y的余数) procedure EXCHANGE(A,n) i←1 j←n repeat

while_________do // 当A[i]为奇数时 // i←i+1 end

while_________do // 当A[i]为偶数时 // j←j-1 end

if(i [ temp←A[i]

A{i}←A[j]

______________ ] // 交换A[i]与A[j]的位置 // else exit

until __________ end

2.(15分) 已知非空线性链表的链结点的构造为 date | link，第一个链结点的指针为list，下面的算法在链表的第i个链结点(设i>0)前插入一个数据信息为item的新结点。请在算法的空白处填入适当内容，使之能够正常工作。 procedure INSERT (list,i,item) if (i=1) then

[ call GETNODE (p) // 申请一个新的链结点 // date (p) ←item link (p) ←list

________________ // 将新结点插在第1个链结点前 // else [ q←list

for j←1 to___________do r←q

q←link (q)

if__________then

[call ERROR (\超过链表的长度!\return ]

end // r与q分别指向第i-1个与第i个链结点 // call GETNODE (p) // 申请一个新的链结点空间 // data (p) ←item link (p) ←q

__________________] // 将新结点插在第i个结点前 // end

本文来源：https://www.bwwdw.com/article/trcw.html