数据结构复习答案2013

《数据结构复习答案2013》由会员分享，可在线阅读，更多相关《数据结构复习答案2013（16页珍藏版）》请在金锄头文库上搜索。

1、1数据结构复习答案数据结构复习答案 一、选择填空一、选择填空 1.下面关于线性表的叙述中，错误的是哪一个？（ ）A）线性表采用顺序存储，必须占用一片连续的存储单元。B）线性表采用顺序存储，便于进行插入和删除操作。C）线性表采用链接存储，不必占用一片连续的存储单元。D）线性表采用链接存储，便于插入和删除操作。 2.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用 （ ）存储方式最节省时间。A）顺序表 B）双链表 C）带头结点的双循环链表 D）单循环链表 3.链表不具有的特点是（ ） 。 A）插入、删除不需要移动元素 B）可随机访问任一元素 C）不必事先估计存储空间

2、 D）所需空间与线性长度成正比 4.若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂 度为（ ）(1next=s;s-next=p-next; B） s-next=p-next;p-next=s;C）p-next=s;p-next=s-next; D） p-next=s-next;p-next=s; 8.设指针变量 p 指向单链表结点 A，则删除结点 A 的后继结点 B 需要的操作为( )。A）p-next=p-next-nextB） p=p-next C）p=p-next-nextD） p-next=p 9.在双向链表指针 p 的结点前插入一个指针 q

3、 的结点操作是（ ） 。 A） p-prior=q;q-next=p;p-prior-next=q;q-prior=q；B） p-prior=q;p-prior-next=q;q-next=p;q-prior=p-prior;C） q-next=p;q-prior=p-prior;p-prior-next=q;p-prior=q; D） q-prior=p-prior;q-next=q;p-prior=q;p-prior=q; 10. 在双向链表存储结构中，删除 p 所指的结点时须修改指针（ ） 。A） (p-prior)-next=p-next (p-next)-prior=p-prior;

4、B） p-prior=(p-prior)-prior (p-prior)-next=p;C） (p-next)-prior=p p-next=(p-next)-next D） p-next=(p-prior)-prior p-prior=(p-next)-next; 11. ( )又称为 FIFO 表；( )又称为 FILO 表。A）队列 B）散列表 C）栈 D）哈希表 12. 对于栈操作数据的原则是（ ） 。 A） 先进先出 B） 后进先出 C） 后进后出 D） 不分顺序 13. 用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点， 则在进行删除操作时( )。A）

5、仅修改队头指针 B） 仅修改队尾指针 C） 队头、队尾指针都要修改 D） 队头、队尾指针都可能要修改214. 假设以数组 Am存放循环队列的元素，其头尾指针分别为 front 和 rear，则当前队列中的元 素个数为（ ） 。A）(rear-front+m)%m B）rear-front+1 C）(front-rear+m)%m D）(rear-front)%m 15. 栈和队列的共同点是（ ） 。 A） 都是先进先出 B） 都是先进后出 C） 只允许在端点处插入和删除元素 D） 没有共同点 16. 设栈 S 和队列 Q 的初始状态为空，元素 e1，e2，e3，e4,e5 和 e6 依次通过栈

6、 S，一个元素出 栈后即进队列 Q，若 6 个元素出队的序列是 e2，e4，e3,e6,e5,e1 则栈 S 的容量至少应该是( )。A） 6 B） 4 C） 3 D） 2 17. 设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a11 为第一元素，其存 储地址为 1，每个元素占一个地址空间，则 a85 的地址为（ ） 。A） 12 B） 33 C） 18 D） 40 18. 设 A 是 n*n 的对称矩阵，将 A 的对角线及对角线上方的元素以列为主的次序存放在一维数组 B1） ）n(n+1)/2中，对上述任一元素 aij(1i，jn，且 ij)在 B 中的位置为( )。

7、A） i(i-l)/2+j B） j(j-l)/2+i C） j(j-l)/2+i-1 D） i(i-l)/2+j-1 19. 由 3 个结点可以构造出多少种不同的二叉树？( )A）2 B）3 C）4 D）5 20. 二叉树中第 i(i1)层上的结点数最多有( )个。 A） 2iB） 2iC） 2i-1D） 2i-1 21. 在有 n 个叶子结点的哈夫曼树中，其结点总数为( )。 A）不确定 B）2n C）2n+1 D）2n-1 22. 一棵二叉树高度为 h，所有结点的度或为 0、或为 2，则这棵二叉树最少有( )结点。 A）2h B）2h-1 C）2h+1 D）h+1 23. 若一棵二叉树具

8、有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是( )。 A）9 B）11 C）15 D）不确定 24. 设树 T 的度为 4，其中度为 1，2，3 和 4 的结点个数分别为 4，2，1，1 则 T 中的叶子数为( )。A）5 B）6 C）7 D）8 25. 树的后根遍历序列等同于该树对应的二叉树的( )。 A） 先序序列 B） 中序序列 C） 后序序列D）层序序列 26. 在下列存储形式中，哪一个不是树的存储形式？( ) A）双亲表示法 B）孩子链表表示法 C）孩子兄弟表示法D）顺序存储表示法 27. 在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的

9、先后顺序( )。 A）都不相同 B）完全相同 C）先序和中序相同，而与后序不同 D）中序和后序相同，而与先序不同 28. 下列哪一种图的邻接矩阵是对称矩阵？( ) A）有向图 B）无向图 C）AOV 网 D）AOE 网 29. 在一个无向图中，所有顶点的度数之和等于所有边数( 2 )倍，在一个有向图中，所有顶点的 入度之和等于所有顶点出度之和的( 1 )倍。A）1/2 B）2 C）1 D）4 30. 一个有 n 个顶点的无向图最多有( )条边。由 n 个顶点组成的有向图，最多可以有( )条边。 A）n*n B）2n C）n(n-1)D）n(n-1)/2 31. 下列说法不正确的是( )。3A）

10、图的遍历是从给定的源点出发每一个顶点仅被访问一次 B）遍历的基本算法有两种：深度遍历和广度遍历 C）图的深度遍历不适用于有向图 D）图的深度遍历是一个递归过程 32. 下面哪一方法可以判断出一个有向图是否有环(回路) ( )。 A）深度优先遍历 B） 拓扑排序 C） 求最短路径 D） 求关键路径 33. 下列算法中，( )算法用来求图中每对顶点之间的最短路径。 A）DijkstraB）FloyedC）PrimD）Kruskal 34. 关键路径是事件结点网络中( )。A）从源点到汇点的最长路径 B）从源点到汇点的最短路径C）最长回路 D）最短回路 35. 若查找每个记录的概率均等，则在具有 n

11、 个记录的连续顺序文件中采用顺序查找法查找一个 记录，其平均查找长度 ASL 为( )。A） (n-1)/2 B） n/2 C） (n+1)/2 D） n 36. 下面关于二分查找的叙述正确的是 ( ) 。 A） 表必须有序，表可以顺序方式存储，也可以链表方式存储 B） 表必须有序，而且只能从小到大排列 C 表必须有序且表中数据必须是整型，实型或字符型 D） 表必须有序，且表只能以顺序方式存储 37. 折半查找的时间复杂性为( ) 。A） O(n2) B） O(n) C） O(nlogn) D） O(logn) 38. 当采用分快查找时，数据的组织方式为 ( ) 。A）数据分成若干块，每块内数

12、据有序B）数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据 组成索引块C） 数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D） 数据分成若干块，每块(除最后一块外)中数据个数需相同 39. 下面关于 B 和 B+树的叙述中，不正确的是( )。 A） B-树和 B+树都是平衡的多叉树 B） B-树和 B+树都可用于文件的索引结构C） B-树和 B+树都能有效地支持顺序检索 D） B-树和 B+树都能有效地支持随机检索 40. 下面关于哈希(Hash，杂凑)查找的说法正确的是( )。A）哈希函数构造的越复杂越好，因为这样随机性好，冲突小B）除留余

13、数法是所有哈希函数中最好的C）不存在特别好与坏的哈希函数，要视情况而定D）若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即 可 41. 下面给出的四种排序法中( )排序法是不稳定性排序法。A） 插入 B） 冒泡 C） 二路归并 D） 堆 42. 稳定的排序方法是( ) 。 A）直接插入排序和快速排序 B）折半插入排序和起泡排序 C）简单选择排序和四路归并排序 D）树形选择排序和 shell 排序 43. 有一组数据(15，9，7，8，20，-1，7，4) 用快速排序的划分方法进行一趟划分后数据的排序4为 ( )(按递增序)。A）下面的 B，C，D 都不对。 B）9，7，8，4，-1，7，15，20C）20，15，8，9，7，-1，4，7 D）9，4，7，8，7，-1，15，20 44. 设有一个文件有 200 个记录，按分块查找法查找记录，如分成 10 块，每块 20 个记录，用二 分查找法查索引表，用顺序查找法查块内记录，则平均查找长度为( )。 A）8）4B）10）5 C）13）4D）16 45. 快速排序在最坏情况下的时间复杂性为( )。 A）O(nlog2n)B）O(n2) C）O(n)D）O(nlogn) 二、填空二、填空1.一个算法的效率可分为 时间时间 效率和 空间空间