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

云南财经大学信息学院

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

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

模拟试题部分

一、单项选择题

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．二叉排序树或是一棵空二叉树，或是具有下列性质的二叉树；若它的左子树非空，则根

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库数据结构习题 - 部分答案 - 全真模拟在线全文阅读。