一、 填空题 （每小题 1 分，共 20 分） ：
1、  栈是一种 _____________的线性表，队列是一种_____________的线性表(要求填特性)。
2、  ___________________是数据的基本单位，可由若干个_______________ 组成，______________是数据的最小单位。
3、  具有 354个结点的完全二叉树深度为 ________________，树中度为1的结点数为______________。
4、  数组的运算有 ______________________________________ 和____________________________。
5、  稀疏矩阵的压缩存储一般采用 _____________________________存储方式。
6、  广义表运算： tail ((( a, b ), ( c , ( d, e )))) = _______________________ 。
7、  数据结构中评价算法的两个重要指标是 __________ 、 __________ 。
8、  一个算法具有 5个特性: 、 、 ，有零个或多个输入、有一个或多个输出。
9、  已知指针 p指向单链表L中的某结点，则删除其后继结点的语句是: 。
10、  Prim（普里姆）算法适用于求 ______ 的网的最小生成树； kruskal（克鲁斯卡尔）算法适用于求 ______ 的网的最小生成树。
11、  N个顶点的连通图的生成树含有 ______ 条边。
12、  顺序查 n个元素的顺序表，若查成功，则比较关键字的次数最多为 __ __ 次；当使用监视哨时，若查失败，则比较关键字的次数为_ _ __ 。
13、  若不考虑基数排序，则在内排序过程中，主要进行的两种基本操作是关键字的 __________ 和记录的 _________ 。
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. 可以唯一的标识一个记录的关键字称为__________。
二、  判断题 ( 如果错误请说明理由，每题 1.5 分，共 15 分 ) ：
1、  度为 2的树就是二叉树。（  ）
2、  内排序中的快速排序算法，在任何情况下都可得到最快的排序效果。（  ）
3、  已知一有向图邻接矩阵 An*n，其顶点Vi的出度为 （  ）
4、  冒泡排序方法和归并排序方法都是稳定的排序方法。（  ）
5、  广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（  ）
6、  堆排序是稳定的排序方法。（  ）
7、  不同的求最小生成树的方法最后得到的生成树是相同的。（  ）
8、  顺序存储方式的优点是存储密
度大，且插入、删除运算效率高。（  ）
9、  栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（  ）
10、  线性表的特点是每个元素都有一个前驱和一个后继。（  ）
三、  单选题 （每题 1.5 分，共 30 分） ：
1 ． 对于 循环队列，下列说法错误的是（  ）
A. 可用顺序存储结构  B. 会产生下溢 
C. 不会产生上溢 D.不会产生假溢
2. 若完全无向图有n 个顶点，则边的数目为（　）：
A. n B. n-1
C. n(n-1)/2 D. n(n-1)
3. 如右图中有向图的深度优先搜索遍历得到的结点序列是（　）
A.1 2 4 6 3 5 B.1 3 2 4 5 6 字符串长度大于5
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
C.15/6
D.21/6
6．从逻辑上可以把数据结构分为（ ）两大类。
A．动态结构、静态结构 B．顺序结构、链式结构
C．线性结构、非线性结构 D．初等结构、构造型结构
7 ． 在下面的程序段中，对 x的赋值语句的频度为（ ）
FOR（i=1；i<=n ;i++）
FOR (j=1;j<= n;j++ )
x=x+1;
A． O(2n) B．O(n) C．O(n 2 ) D．O(log 2 n )
8 . 以下数据结构中，（ ）是非线性数据结构
A．树 B．字符串 C．队 D．栈
9 . 若某线性表最常用的操作是存取 任一指 定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
10. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。
A．p->next=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;
11. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。
A. 不确定 B. n-i+1 C. i D. n-i
12. 循环队列存储在数组]中，则入队时的操作为（ ）。
A. rear=rear+1 B. rear=(rear+1) mod (m-1)
C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)
13. 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
A．求子串 B．联接 C．匹配 D．求串长
14. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，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的结点个数是（ ）
A．9 B．11 C．15 D．不确定
18. 已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为 （ ）。
A．CBEFDA 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、  简述平衡二叉树特点及其平衡调整规律方法
3、  写出右图二叉树的先序、中序、后序遍历序列
4、  除留余数法对给定关键字
（ 10 ， 8 ， 17 ， 16 ， 4 ， 7 ， 25 ， 18 ）进行哈希制表，地址空间为 0 ～ 9 ，以除留余数法构造哈希函数，线性探查法解决冲突，画出哈希表并计算查成功的平均查长度。
5、  写出用直接插入排序对关键字序列（ 53,24,45,64,51, 24 ,95,36 ）进行排序的每一趟结果。
五、  编程题 （ 10 分）
1、  编写在递增有序的线性链表 La 中插入元素 x 的算法 ( 插入后仍然有序 ) 。（ 5 分）
2、  写出求二叉树 T 中叶子个数的算法。（ 5 分）
模拟试题二
《数据结构》期末考试试题
（ 120 分钟）
题号
一
二
三
四
五
总分
题分
20
15
30
25
10
得分
一、  填空题 （每小题 1 分，共 20 分） ：
1、  分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是 _____算法，最费时间的是______算法。
2、  已知二叉排序树的左右子树均不为空，则 __________上所有结点的值均小于它的根结点值，__________上所有结点的值均大于它的根结点的值。
3、  设有一个空栈，栈顶指针为 1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_______，而栈顶指针值是_______H。设栈为顺序栈，每个元素占4个字节。
4、  循环队列用数组 -1]存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是 _______ 。
5、  在单链表 L中，指针p所指结点有后继结点的条件是：_ _ 。
6、  快速排序在 _____的情况下最易发挥其长处。
7、  在一个长度为 n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。
8、  下面程序段的时间复杂度为 ________。(n>1)
sum=1；
for (i=0;sum<n;i++) sum+=1;
9、  当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 _______存储结构。
10、  在双向循环链表中 ，向p所指的结点之后插入指针f所指的结点，其操作是_______、_______、_______、________。
11、  _______ 是限定仅在表尾进行插入或删除操作的线性表。
12、  循环队列的引入，目的是为了克服 _______ 。
13、  两个字符串相等的充分必要条件是 _______。
14、  已知数组 A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[6，8]的地址为_______。
15、  上三角矩阵压缩的下标对应关系为： _______。
16、  空格串的长度为 ________。
17、  具有 256个结点的完全二叉树的深度为 ______ 。
18、  对于一个具有 n个结点的二叉树，当它为一棵 _ _ 时具有最小高度，当它为一棵 _ _ 时，具有最大高度。
19、  求图的最小生成树有两种算法，____________算法适合于求稠密图的最小生成树。
20、  在 n个记录的有序顺序表中进行折半查，最大比较次数是__________。
二、  判断题 ( 如果错误请说明理由，每题 1.5 分，共 15 分 ) ：
1、  数据元素是数据的最小单位。 ( )
2、  内排序中的快速排序算法，并不是在任何情况下都可得到最快的排序效果。（ ）
3、  数据的物理结构是指数据在计算机内的实际存储形式。 ( )
4、  顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。 ( )
5、  两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（ ）
6、  若一个广义表的表尾为空表，则此广义表亦为空表。 （ ）
7、  对一棵二叉树进行层次遍历时，应借助于一个栈。（ ）
8、  采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。（ ）
9、  连通分量指的是有向图中的极大连通子图。（ ）
10、  查相同结点的效率折半查总比顺序查高。（ ）
三、  单选题 （每题 1.5 分，共 30 分） ：
1 ． 设哈希表长为 14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )
A．8 B．3 C．5 D．9
2. 若完全无向图有n 个顶点，则边的数目为（　）：
A. n B. n-1
C. n(n-1)/2 D. n(n-1)
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. 冒泡 B. 希尔插入 C. 交换 D. 快速
5． 哈希查中 k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行( )次探测。
A． k B. k+1 C. k(k+1)/2 D.1+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) B．O(n) C．O(n 2 ) D．O(log 2 n )
8 . 二叉查树的查效率与二叉树的( )有关。
A. 高度 B. 结点的多少 C. 树型 D. 结点的位置
9 . 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。
A ． G中有弧<Vi，Vj> B ． G中有一条从Vi到Vj的路径
C ． G中没有弧<Vi,Vj> D ． G中有一条从Vj到Vi的路径
10. 下面哪一方法可以判断出一个有向图是否有环（回路）:( )
A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 广度优先遍历
11. 当一棵有 n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 ]中时，数组中第i个结点的左孩子为（ ）
A．A[2i](2i=<n) B. A[2i+1](2i+1=< n) C．A[i/2] D．无法确定
12. 下面的说法中正确的是（ ）.
（ 1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；
（ 2）按二叉树定义，具有三个结点的二叉树共有6种。
A．(1)(2) B．(1) C．(2) D．(1)、(2)都错
13. 以下与数据的存储结构无关的术语是（ ）。
A．循环队列 B. 链表 C. 哈希表 D. 栈
14. 在完全二叉树中，若一个结点是叶结点，则它没（ ）。
A．左子结点 B．右子结点  C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点
15. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )。
A. 0 B. 1 C. 2 D. 不确定
16. 广义表（（a,b,c,d））的表尾是（ ）。
A. d B.（d） C.（a,b,c,d） D.((a,b,c,d）)
17. 下列哪一种图的邻接矩阵是对称矩阵？（ ）
A．有向图 B．无向图 C．AOV网 D．AOE网
18. 下列说法不正确的是（ ）。
A ． 图的遍历是从给定的源点出发每一个顶点仅被访问一次
B ． 图的深度遍历不适用于有向图
C ．图 遍历的基本算法有两种：深度遍历和广度遍历
D ． 图的深度遍历

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。