2022年数据结构模拟试题资料 .pdf

《2022年数据结构模拟试题资料 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构模拟试题资料 .pdf（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、模拟试题一数据结构期末考试试题（ 120 分钟）题号一二三四五总分题分20 15 30 25 10 得分一、 填空题（每小题1 分，共20 分） ：1、栈是一种_的线性表，队列是一种_的线性表 ( 要求填特性 )。2、_是数据的基本单位，可由若干个_ 组成，_是数据的最小单位。3、具有 354 个结点的完全二叉树深度为_，树中度为1 的结点数为_。4、数组的运算有_ 和_。5、稀疏矩阵的压缩存储一般采用_存储方式。6、广义表运算：tail ( a, b ), ( c , ( d, e ) = _ 。7、数据结构中评价算法的两个重要指标是_ 、 _ 。8、一个算法具有5 个特性 : 、 、 ，有

2、零个或多个输入、有一个或多个输出。9、已知指针p 指向单链表L 中的某结点，则删除其后继结点的语句是: 。10 、Prim （普里姆）算法适用于求_ 的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求 _ 的网的最小生成树。11 、N 个顶点的连通图的生成树含有_ 条边。12 、顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_ _ 次；当使用监视哨时，若查找失败，则比较关键字的次数为_ _ _ 。13 、若不考虑基数排序，则在内排序过程中，主要进行的两种基本操作是关键字的_ 和记名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -

3、- - - - - - 名师精心整理 - - - - - - - 第 1 页，共 40 页 - - - - - - - - - 录的 _ 。14 、直接插入排序用监视哨的作用是_。15 、一个字符串中_ 称为该串的子串。16 . 广义表 (a,(a,b),d,e,(i,j),k)的长度是_ ，深度是_ 。17. 在二叉树中，指针p 所指结点为叶子结点的条件是_ 。18. 有数据 WG=7，19 ，2，6，32 ，3 ，21 ，10 ，则所建 Huffman树的树高是_ _ ，带权路径长度 WPL 为 _ _ 。19. 求图的最小生成树有两种算法，_ 算法适合于求稀疏图的最小生成树。20. 可以

4、唯一的标识一个记录的关键字称为_。二、判断题( 如果错误请说明理由，每题1.5 分，共15 分 ) ：1、度为 2 的树就是二叉树。（）2、内排序中的快速排序算法，在任何情况下都可得到最快的排序效果。（）3、已知一有向图邻接矩阵An*n ，其顶点 Vi 的出度为（）4、冒泡排序方法和归并排序方法都是稳定的排序方法。（）5、广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（）6、堆排序是稳定的排序方法。（）7、不同的求最小生成树的方法最后得到的生成树是相同的。（）8、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）9、栈和队列的存储方式，既可以是顺序方式，又可以是链式方

5、式。（）10 、线性表的特点是每个元素都有一个前驱和一个后继。（）三、单选题（每题1.5 分，共30 分） ：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 40 页 - - - - - - - - - 1 对于 循环队列，下列说法错误的是（）A. 可用顺序存储结构B. 会产生下溢C. 不会产生上溢D. 不会产生假溢2. 若完全无向图有n 个顶点，则边的数目为（）：A. n B. n-1 C. n(n-1)/2 D. n(n-1) 3. 如右图中有向图的深度优先搜索遍历得

6、到的结点序列是（）A.1 2 4 6 3 5 B.1 3 2 4 5 6 C.1 2 3 4 5 6 D. 1 3 2 6 4 5 4. 下列说法中符合队列性质的是（）A. 先进後出B. 只能在一边插入和删除C.只能为顺序结构D. 只能在一边插入和另一边删除5如图 BST 树成功的平均查找长度为（）A.21/7 B.18/7 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 40 页 - - - - - - - - - C.15/6 D.21/6 6从逻辑上可以把数据结构分

7、为（）两大类。A动态结构、静态结构B顺序结构、链式结构C线性结构、非线性结构D 初等结构、构造型结构7 在下面的程序段中，对x 的赋值语句的频度为（）FOR（i=1 ；i=n ;i+）FOR (j=1;jnext=s;s-next=p-next; B s-next=p-next;p-next=s; Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s; 11. 一个栈的输入序列为123 n，若输出序列的第一个元素是n，输出第 i（1=i=n）个元素是 （ ）。A. 不确定B. n-i+1 C. i D. n-i 12. 循环队列存储在数组A0.m中

8、，则入队时的操作为（）。A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 40 页 - - - - - - - - - 13. 设有两个串p 和 q，其中 q 是 p 的子串，求q 在 p 中首次出现的位置的算法称为（）A求子串B联接C匹配D求串长14. 数组 A0.5,0.6的每个元素占五个字节

9、， 将其按列优先次序存储在起始地址为1000 的内存单元中，则元素 A5 ，5 的地址是 ( ) 。A. 1175 B. 1180 C. 1200 D. 1210 15. 对稀疏矩阵进行压缩存储目的是（）。A便于进行矩阵运算B便于输入和输出C节省存储空间D降低运算的时间复杂度16. 设广义表L= （ a,b,c ），则 L 的长度和深度分别为（）。A. 1 和 1 B. 1和 3 C. 1和 2 D. 2和 3 17. 若一棵二叉树具有10 个度为 2 的结点， 5 个度为 1 的结点，则度为0 的结点个数是（）A9 B 11 C 15 D 不确定18. 已知一棵二叉树的前序遍历结果为ABCD

10、EF, 中序遍历结果为CBAEDF, 则后序遍历的结果为（ ）。ACBEFDA B FEDCBA C CBEDFA D 不定19. 具有 12 个关键字的有序表，折半查找的平均查找长度（）A. 3.5 B. 4 C. 2.5 D. 5 20. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A, 并已知 A 的左孩子的平衡因子为 0 右孩子的平衡因子为1, 则应作 ( ) 型调整以使其平衡。A. LL B. LR C. RL D. RR 四、应用题（每题5 分，共 25 分）1、比较顺序存储和链式存储的优缺点。2、简述平衡二叉树特点及其平衡调整规律方法名师资料总结 - - -精品

11、资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 40 页 - - - - - - - - - 3、写出右图二叉树的先序、中序、后序遍历序列4、除留余数法对给定关键字（ 10 ， 8 ， 17 ， 16 ， 4 ， 7 ， 25 ， 18 ）进行哈希制表，地址空间为0 9 ，以除留余数法构造哈希函数，线性探查法解决冲突，画出哈希表并计算查找成功的平均查找长度。5、写出用直接插入排序对关键字序列（53,24,45,64,51, 24 ,95,36 ）进行排序的每一趟结果。五、编程题（ 10 分）1、编写

12、在递增有序的线性链表La 中插入元素x 的算法( 插入后仍然有序) 。（ 5 分）2、写出求二叉树T 中叶子个数的算法。（5 分）模拟试题二数据结构期末考试试题（ 120 分钟）题号一二三四五总分题分20 15 30 25 10 得分一、填空题（每小题1 分，共20 分） ：1、分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_ 算法，最费时间的是_算法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 40 页 - - - - - - - -

13、 - 2、已知二叉排序树的左右子树均不为空，则_上所有结点的值均小于它的根结点值，_上所有结点的值均大于它的根结点的值。3、设有一个空栈，栈顶指针为1000H(十六进制 )，现有输入序列为1 ，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后， 输出序列是 _，而栈顶指针值是_H。设栈为顺序栈，每个元素占4 个字节。4、循环队列用数组A0.m-1存放其元素值，已知其头尾指针分别是front和 rear ，则当前队列的元素个数是_ 。5、在单链表L 中，指针 p 所指结点有后继结点的条件是：_ _ 。6、快速排序在_ 的情况下最易发挥其长处。7、在一个长度

14、为n 的顺序表中第i 个元素（ 1=i1) sum=1；for (i=0;sumn;i+) sum+=1; 9、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_存储结构。10 、在双向循环链表中,向 p 所指的结点之后插入指针f 所指的结点，其操作是_、_、_、_。11 、_ 是限定仅在表尾进行插入或删除操作的线性表。12 、循环队列的引入，目的是为了克服_ 。13 、两个字符串相等的充分必要条件是_。14 、已知数组A0.9,0.9的每个元素占5 个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A6 ，8 的

15、地址为 _。15 、上三角矩阵压缩的下标对应关系为：_。16 、空格串的长度为_。17 、具有 256 个结点的完全二叉树的深度为_ 。18 、对于一个具有n 个结点的二叉树，当它为一棵_ _ 时具有最小高度，当它为一棵_ _ 时，具有名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 40 页 - - - - - - - - - 最大高度。19 、求图的最小生成树有两种算法，_算法适合于求稠密图的最小生成树。20 、在 n 个记录的有序顺序表中进行折半查找，最大比较次数是_

16、。二、判断题( 如果错误请说明理由，每题1.5 分，共15 分 ) ：1、数据元素是数据的最小单位。( ) 2、内排序中的快速排序算法，并不是在任何情况下都可得到最快的排序效果。（）3、数据的物理结构是指数据在计算机内的实际存储形式。( ) 4、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( ) 5、两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（）6、若一个广义表的表尾为空表，则此广义表亦为空表。（ ）7、对一棵二叉树进行层次遍历时，应借助于一个栈。（）8、采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍

17、历的结果是一样的。（）9、连通分量指的是有向图中的极大连通子图。（）10 、查找相同结点的效率折半查找总比顺序查找高。（）三、单选题（每题1.5 分，共30 分） ：1 设哈希表长为14 ，哈希函数是H(key)=key%11,表中已有数据的关键字为15 ，38 ，61 ，84 共四个，现要将关键字为49 的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( ) A8 B 3 C 5 D 9 2. 若完全无向图有n 个顶点，则边的数目为（）：A. n B. n-1 C. n(n-1)/2 D. n(n-1) 3. 如右图中有向图的广度度优先搜索遍历得到的结点序列是（）名师资料总结 -

18、- -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 40 页 - - - - - - - - - A.1 2 4 6 3 5 B.1 3 2 4 5 6 C.1 2 3 4 6 5 D. 1 3 2 6 4 5 4. 就平均性能而言，目前最好的内排序方法是( ) 排序法。A. 冒泡 B. 希尔插入C. 交换 D. 快速5 哈希查找中k 个关键字具有同一哈希值，若用线性探测法将这k 个关键字对应的记录存入哈希表中，至少要进行 ( ) 次探测。A k B. k+1 C. k(k+1)/2 D.1+

19、k(k+1)/2 6分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) A（ 100 ，80 ， 90 ， 60 ， 120 ，110 ，130 ） B. （100 ，120 ，110 ，130 ， 80 ， 60 ， 90 ）C.（100 ，60 ， 80 ， 90 ， 120 ，110 ，130 ） D. (100，80 ， 60 ， 90 ， 120 ，130 ，110) 7 在下面的程序段中，对x 的赋值语句的频度为（）FOR（i=1 ；i=n ;i+）FOR (j=1;j= 100;j+ ) x=x+1; A O(2n) BO(n) CO(n 2 ) DO(lo

20、g 2 n ) 8 . 二叉查找树的查找效率与二叉树的( ) 有关。A. 高度 B. 结点的多少C. 树型 D. 结点的位置9 . 在有向图 G 的拓扑序列中，若顶点Vi 在顶点 Vj 之前，则下列情形不可能出现的是（）。A G 中有弧 B G 中有一条从Vi 到 Vj 的路径C G 中没有弧 D G 中有一条从Vj 到 Vi 的路径10. 下面哪一方法可以判断出一个有向图是否有环（回路）:( ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 40 页 - - - -

21、- - - - - A深度优先遍历B. 拓扑排序C. 求最短路径D. 广度优先遍历11. 当一棵有n 个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组Al.n中时，数组中第 i 个结点的左孩子为（）AA2i(2i=n) B. A2i+1(2i+1=j)对应的 B 中存储位置为 _。7、深度为k 的完全二叉树至少有_ 个结点，至多有_ 个结点。8、如果结点A 有 3 个兄弟，而且B 是 A 的双亲，则B 的度是_ 。9、若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的_ 序列中的最后一个结点。10 、在双向循环链表中,向 p 所指的结点之前插入指针f

22、 所指的结点，其操作是_、_、_、_。11 、_ 是限定仅在表尾进行插入以及在表头进行删除操作的线性表。12 、G 是一个非连通无向图，共有28 条边，则该图至少有_ 个顶点。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 40 页 - - - - - - - - - 13 、线索二叉树的左线索指向其_ ，右线索指向其_ 。14 、在有序表A1 20 中，按二分查找方法进行查找，查找长度为4 的元素的下标从小到大依次是_ 。15 、执行顺序查找时，储存方式可以是_ _

23、_ _，二分法查找时，要求线性表_ _ _ _ 。16 、顺序查找用监视哨的作用是_。17 、在单链表中设置头结点的作用是_。18 、对于一个具有n 个结点的二叉树，当它为一棵_ _ 时具有最小高度，当它为一棵_ _ 时，具有最大高度。19 、从平均时间性能而言，_排序最佳。20 、顺序栈用data1.n存储数据，栈顶指针是top, 则值为 x 的元素入栈的操作是_。二、判断题( 如果错误请说明理由，每题1.5 分，共15 分 ) ：1、数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. ( ) 2、两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈

24、底分别设在这片内存空间的两端。（）3、取线性表的第i 个元素的时间同i 的大小有关 . ( ) 4、二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该树的根结点是那一个，则可以确定这棵二叉树。（）5、对无序表用二分法查找比顺序查找快。（）6、通常使用队列来处理函数或过程的调用。（）7、在 n 个结点的无向图中，若边数大于n-1, 则该图必存在环路。（）8、采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。（）9、带权无向图的最小生成树必是唯一的。（ ）10 、顺序查找法适用于存储结构为顺序或链接存储的线性表。（）三、单选题（每题1.5 分，共30 分） ：

25、1 算法的时间复杂度取决于（ ）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 40 页 - - - - - - - - - A问题的规模B. 待处理数据的初态C. A 和 B 2. 线性表是具有n 个（ ）的有限序列（n0 ）。A表元素B字符C数据元素D数据项3. 如右图中有向图的广度度优先搜索遍历得到的结点序列是（）A.1 2 4 6 3 5 B.1 3 2 4 5 6 C.1 2 3 4 6 5 D. 1 3 2 6 4 5 4. 以下属于逻辑结构的是（）。A顺序

26、表B. 哈希表C.有序表D. 单链表5 (1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i 个元素的时间与i无关。(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（）A（ 1），（ 2） B（ 1 ） C（ 1 ），（ 2）,(3) D.（ 2）6 有一个100*90的稀疏矩阵，非0 元素有 10 个，设每个整型数占2 字节，则用三元组表示该矩阵时，所需的字节数是（）。A. 60 B. 66 C. 18000 D. 33 7 下面说法不正确的是( ) 。A.

27、广义表的表头总是一个广义表B. 广义表的表尾总是一个广义表C. 广义表难以用顺序存储结构D. 广义表可以是一个多层次的结构8 . 设树 T 的度为 4，其中度为 1 ，2，3 和 4 的结点个数分别为4，2 ，1 ，1 则 T 中的叶子数为（）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 40 页 - - - - - - - - - A5 B 6 C 7 D 8 9 . 二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK ；中序遍历 : HFIEJKG 。该二叉

28、树根的右子树的根是：（ ）A、 E B 、 FC、 GD 、 H 10. 要连通具有n 个顶点的有向图，至少需要（）条边。An-l B n C n+l D2n 11. 当一个有n 个顶点的有向图用邻接矩阵A 表示时，顶点Vi 的度是（）。ABCD+ 12. 当采用分块查找时，数据的组织方式为( ) A数据分成若干块，每块内数据有序B数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D. 数据分成若干块，每块（除最后一块外）中数据个数需相同13. 在平衡二叉树中插入一个结点后造成了不平

29、衡，设最低的不平衡结点为A, 并已知 A 的左孩子的平衡因子为 0 右孩子的平衡因子为1, 则应作 ( ) 型调整以使其平衡。A. LL B. LR C. RL D. RR 14. 某内排序方法的稳定性是指( ) 。A该排序算法不允许有相同的关键字记录B该排序算法允许有相同的关键字记录C平均时间为0 （n log n）的排序方法D以上都不对15. 排序趟数与序列的原始状态有关的排序方法是( ) 排序法。A插入B. 选择 C. 冒泡 D. 快速名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -

30、 第 15 页，共 40 页 - - - - - - - - - 16. 下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( ) 排序。A 冒泡B. 希尔 C. 快速D. 堆17. 下列哪一种图的邻接矩阵是对称矩阵？（）A有向图BAOV 网 C无向图DAOE 网18. 在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为( ) 。A. O(n) B. O(n+e) C. O(n 2 ) D. O(n 3 ) 19. 若串 S= soft,其子串的数目是（）。A8 B 11 C 10 D 9 20. 用单链表表示的链式队列的队头在链表的（）位置。A 链头 B 链尾 C 链中

31、D. 任意位置四、应用题（每题5 分，共 25 分）1、已知如下程序段for (i= 0;in;i+) 语句1 x:=x+1 ； 语句2 for( j=i;jn;j+) 语句3 y=y+1; 语句 4 语句 1 执行的频度为；语句 2 执行的频度为；语句 3 执行的频度为；语句 4 执行的频度为。2、如果两个串含有相等的字符，能否说它们相等？3、三维数组A1.10,-2.6,2.8的每个元素的长度为4 个字节， 试问该数组要占多少个字节的存储空间？如果数组元素以行优先的顺序存贮，设第一个元素的首地址是100 ，试求元素A5,0,7 的存贮首地址。4、设 G=(V,E)以邻接表存储，如图所示，试

32、给出该图的深度优先和广度优先遍历序列。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 40 页 - - - - - - - - - 5、已知一棵二叉树的先序和后序序列如下：先序遍历序列：A B D F C E G H 中序遍历序列：B F D A G E H C （ 3 分) 给出这棵二叉树：（ 2 分) 转换为对应的森林：五、编程题（ 10 分，每小题5 分）1、试用类C 语言编写顺序查找的算法。2、请写出在一个递增有序的单链表La 中插入一个元素x 的类 C 语言算

33、法，要求插入后链表仍然递增有序。模拟试题四数据结构期末考试试题（ 120 分钟）题号一二三四五总分题分20 15 30 25 10 得分一、 填空题（每小题1 分，共20 分） ：1、_是数据的基本单位，_是数据的最小单位。2、已知二叉排序树的左右子树均不为空，则_上所有结点的值均小于它的根结点值，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 40 页 - - - - - - - - - _上所有结点的值均大于它的根结点的值。3、计算机执行下面的语句时，语句s 的执行

34、次数为_ 。FOR(i=l；i=1;j-) s; 4、设单链表的结点结构为(data,next)，next为指针域，已知指针px 指向单链表中data 为 x 的结点，指针 py 指向 data为 y 的新结点, 若将结点 y 插入结点 x 之后，则需要执行以下语句:_； _; 5、带头结点的双循环链表L 中只有一个元素结点的条件是：_ 。6、一个栈的输入序列是：1 ，2，3 则不可能的栈输出序列是_ 。7、_又称作先进先出表。8、设循环队列用数组A0.M-1表示，队首、 队尾指针分别是FRONT 和 TAIL ，判定队满的条件为_。9、一个字符串中_ 称为该串的子串10 、对于一个具有n 个

35、结点的二叉树，当它为一棵_ _ 时具有最小高度，当它为一棵_ _ 时，具有最大高度。11 、数组的存储结构一般采用_存储方式。12 、设某广义表H= （A，（ a,b,c ） ，运用 head 函数和 tail 函数求出广义表H 中某元素 b 的运算式_。13 、假设根结点的层数为，具有个结点的二叉树的最大高度是_ 。14 、已知数组A0.9,0.9的每个元素占3 个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A6 ，7 的地址为 _。15 、含 4 个度为 2 的结点和 5 个叶子结点的二叉树，可有_ 个度为 1 的结点。16 、若以 4 ，5 ，6，7 ，8

36、 作为叶子结点的权值构造哈夫曼树，则其带权路径长度是_ 。17 、INDEX （ DATASTRUCTURE， STR ）= _ 。18 、在有 n 个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要_ 条弧。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 40 页 - - - - - - - - - 19 、Prim （普里姆）算法适用于求_ 的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求 _ 的网的最小生成树。20 、在哈希函数H（key ）=k

37、ey%p中， p 值最好取 _。二、判断题( 如果错误请说明理由，每题1.5 分，共15 分 ) ：1、健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( ) 2、链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。( ) 3、若输入序列为1，2，3 ，4 ，5，6 ，则通过一个栈可以输出序列1，5 ，4 ，6，2 ，3。（）4、队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（）5、广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（）6、完全二叉树一定存在度为1 的结点。（）7、在待排数据基本有序的情况下，快速

38、排序效果最好。（ ）8、在 BST 树 （二叉树排序树 ）中插入一个新结点，总是插入到叶结点下面。（）9、拓扑排序的有向图中，最多存在一条环路。（）10 、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（ ）三、单选题（每题1.5 分，共30 分） ：1 链表不具有的特点是（）A插入、删除不需要移动元素B可随机访问任一元素C不必事先估计存储空间D 所需空间与线性长度成正比2. 一个栈的输入序列为123 n ，若输出序列的第一个元素是n ，输出第 i（1=iprior=q;q-next=p;p-prior-next=q;q-prior=q；B.p-prior=q;p-prior-

39、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; 7 折半查找的时间复杂性为（）A. O （n 2 ） B. O （n ） C. O （nlog n ） D. O （log n ）8 . 在用邻接表表示图时，拓扑排序算法时间复杂度为( ) 。A. O(n) B. O(ne) C. O(n*n) D. O(n*n*n) 9 . 设图如右所示， 在下面的5 个序列中， 符合深度优先遍

40、历的序列有多少？（ ）a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 40 页 - - - - - - - - - A 5 个 B 4 个 C 3 个 D 2 个10. 下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。A二叉排序树B哈夫曼树CAVL 树 D堆11. n个结点的线索二叉树上含有的线索数为（）A

41、2n B nl C n l D n 12. 串的长度是指（）A串中所含不同字母的个数B串中所含字符的个数C串中所含不同字符的个数D串中所含非空格字符的个数13. 栈和队都是（）A顺序存储的线性结构B. 链式存储的非线性结构C. 限制存取点的线性结构D. 限制存取点的非线性结构14. 循环链表H 的尾结点 P 的特点是（）。AP-NEXT = H BP-NEXT = H-NEXT CP = H DP = H-NEXT 15. 以下数据结构中，哪一个是线性结构（）？A广义表B. 二叉树C. 稀疏矩阵D. 串16. 适用于折半查找的表的存储方式及元素排列要求为( ) A链接方式存储，元素无序B链接方

42、式存储，元素有序C顺序方式存储，元素无序D顺序方式存储，元素有序17. 下列排序算法中，其中（）是稳定的。A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 40 页 - - - - - - - - - 18. 下列说法不正确的是（）。A 图的遍历是从给定的源点出发每一个顶点仅被访问一次B 图的深度遍历不适用于有向图C 遍历的基本算法有两种：深度遍历和广度遍历D 图的深度遍历是一

43、个递归过程19. 直接插入排序在最好情况下的时间复杂度为（）A O(logn) B O(n) C O(n*logn) D O(n 2 ) 20. 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( ) 最节省时间。A. 单链表B. 单循环链表C. 带尾指针的单循环链表D. 带头结点的双循环链表四、应用题（每题5 分，共 25 分）1、什么叫数据结构（广义）？2、有 5 个元素，其入栈次序为：A，B，C，D ，E，在各种可能的出栈次序中，以元素C，D 最先出栈（即 C 第一个且 D 第二个出栈）的次序有哪几个？3、假设用于通信的电文由字符集a,b,c,d,e,f,g中的字母构成。它们在

44、电文中出现的频度分别为0.31,0.16,0.10,0.08,0.11,0.20,0.04, 1) 为这 7 个字母设计哈夫曼编码；2）对这 7 个字母进行等长编码，至少需要几位二进制数？哈夫曼编码比等长编码使电文总长压缩多少？4、如图 G：（ 1）画出G 的邻接表表示图；（ 2）根据你画出的邻接表，以顶点为根，画出G 的深度优先生成树。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 40 页 - - - - - - - - - 5、对于输入关键字序列48 ，70 ，6

45、5 ，33 ，24 ，56 ，12 ，92 建立堆排序的初始堆（小根堆），要求画出主要过程。五、编程题（ 10 分）1、写出直接插入排序的类C 语言算法。2、试写出在单链表La 中删除第i 个结点的类C 语言算法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 40 页 - - - - - - - - - 参考答案名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第

46、 24 页，共 40 页 - - - - - - - - - 模拟试题一一 填空题：1 、先进后出先进先出2 、数据元素数据项数据项3 、 9 1 4 、存取元素修改元素5 、三元组表6 、 (c,(d,e) 7 、时间复杂度空间复杂度8 、有穷性、确定性、可行性9 、 p-next = p-next-next 10 、边稠密边稀疏11 、 N-1 12 、 n n+1 13 、比较搬移14 、防止下标越界和保存副本15 、任意个连续字符16 、 5 3 17 、 p-lchild = = null & p-rchild = = null 18 、310 19 、 Kruskal 名师资料总结

47、 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 25 页，共 40 页 - - - - - - - - - 20 、主关键字二、判断题1 、错；二叉树是有序树，而且二叉树中不一定存在度为二的结点。2 、错；不一定，比如当待排序列有序时，快速排序蜕变为冒泡排序。3 、对。4 、对。5 、错；广义表的取表尾运算必定是广义表。6 、错；对排序不是稳定的排序方法。7 、错；不一定，因为一个连通网的最小生成树并不是唯一的。8 、错；顺序存储插入和删除运算需要移动大量元素，效率比较低。9 、对。10 、错；

48、除了第一个之外，每个都有唯一的直接前驱；除了最后一个之外，每个都有唯一的直接后继。三、单选题1 、 C 2 、 C 3 、 A 4 、 D 5 、 B 6 、 C 7 、 C 8 、 A 9 、 A 10 、 B 11 、 B 12 、 C 13 、 C 14 、 C 15 、 C 16 、 C 17 、 B 18 、 C 19 、 A 20 、 B 四、应用题1 、答： 1 ）顺序存储的优点：随机存取，单元素存储密度大缺点：需要连续存储空间，定义时需要决定大小，不易于扩充，插入删除需要移动大量元素；2 ）链式存储优点：插入删除不需移动元素仅需改变指针，动态申请空间，易于扩充；缺点：顺序存取，

49、需要用指针表示逻辑关系。由上述可见，两种存储结构的优缺点是相反的。2 、平衡二叉树特点：是二叉排序树，任一子树的左子树和右子树的高度差不超过1 。平衡调整方法：LL 调整、RR 调整、LR 调整、RL 调整名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 26 页，共 40 页 - - - - - - - - - 3 、先序序列：5321476 中序序列：2134567 后序序列：1243675 4 、表长为10 ，取 p = 7; 哈希表如下：地址0 1 2 3 4 5 6 7 8

50、9 Key 7 8 16 10 17 4 25 18 查找长度1 1 1 1 2 2 3 4 ASL 成功 = （ 1+1+1+1+2+2+3+4 ） /8 = 15/8 5 、第一趟：24 53 45 64 51 24 95 36 第二趟：24 45 53 64 51 24 95 36 第三趟：24 45 53 64 51 24 95 36 第四趟：24 45 51 53 64 24 95 36 第五趟：24 24 45 51 53 64 95 36 第六趟：24 24 45 51 53 64 95 36 第七趟：24 24 36 45 51 53 6495 五、编程题1 、 Status