数据结构模拟题及答案

一、 填空题 （每小题 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

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 C

11. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。

A. 不确定 B. n-i+1 C. i D. n-i

12. 循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。

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．求串长

．

p->next=s;p->next=s->next;

D． p->next=s->next;p->next=s;

．

p->next=s;s->next=p->next;

B． s->next=p->next;p->next=s;

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,,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、 循环队列用数组 A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是 _______ 。

5、 在单链表 L中，指针p所指结点有后继结点的条件是：_ _ 。

6、 快速排序在 _____的情况下最易发挥其长处。

7、 在一个长度为 n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。

8、 下面程序段的时间复杂度为 ________。(n>1)

sum=1；

for (i=0;sum

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中有弧 B ． G中有一条从Vi到Vj的路径

C ． G中没有弧 D ． G中有一条从Vj到Vi的路径

10. 下面哪一方法可以判断出一个有向图是否有环（回路）:( )

A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 广度优先遍历

11. 当一棵有 n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 A[l..n]中时，数组中第i个结点的左孩子为（ ）

A．A[2i](2i=

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 ． 图的深度遍历

是一个递归过程

19. 下列排序方法中，哪一个是稳定的排序方法？（ ）

A．直接插入排序 B．堆排序 C．希尔排序 D．快速排序

20. 当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )

A．必定快 B.不一定

C. 在大部分情况下要快 D. 取决于表递增还是递减

四、 应用题 （每题 5分，共25分）

1、 数据结构是一门研究什么内容的学科？

2、 已知含有 8个结点的一棵二叉树，按先序、中序、后序进行遍历后，有些结点序号不清楚如下图示。要求构造出一棵符合条件的二叉树。

先根序遍历 _ 2 3 _ 5 _ 7 8

中根序遍历 3 _ 4 1 _ 7 8 6

后根序遍历 _ 4 2 _ _ 6 5 1

3、 假设用于通信的电文由字符集 {a,b,c,d,e,f,g}中的字母构成。它们在电文中出现的频度分别为{0.31,0.16,0.10,0.08,0.11,,0.20,0.04},为这7个字母设计哈夫曼编码；

4、 设 G=(V,E)以邻接表存储，如图所示，试画出图的深度优先和广度优先生成树。

5、 用序列 (46,88,45,39,70,58,101,10,66,34)建立一个BST树，画出该树，并求在等概率情况下查找成功的平均查找长度 。

五、 编程题 （ 10 分）

编 函数 void insert(char*s,char*t,int pos)将字符串t插入到字符串s中，插入位置为pos。请用c语言实现该函数。假设分配给字符串s的空间足够让字符串t插入。（说明：不得使用任何库函数）

模拟试题三

《数据结构》期末考试试题

（ 120 分钟） 题号 一 二 三 四 五 总分 题分 20

15 30 25 10 得分

一、 填空题 （每小题 1 分，共 20 分） ：

1、 对于一个具有 n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。

2、 链式存储的特点是利用 ________来表示数据元素之间的逻辑关系。

3、 对矩阵压缩是为了 _______。

4、 已知广义表 LS=(a，(b，c，d)，e),运用head和tail函数取出LS中原子b的运算是_______。

5、 在单链表 L中，指针p所指结点没有后继结点的条件是：_ _ 。

6、 设 n行n列的下三角矩阵A已压缩到一维数组B[0..n*（n+1）/2-1]中，若按行为主序存储，则A[i,j](i>=j)对应的B中存储位置为_______。

7、 深度为 k的完全二叉树至少有 _______ 个结点，至多有 _______ 个结点。

8、 如果结点 A有 3个兄弟，而且B是A的双亲，则B的度是 ______ 。

9、 若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的 ______ 序列中的最后一个结点。

10、 在双向循环链表中 ,向p

所指的结点之前插入指针f所指的结点，其操作是_______、_______、_______、________。

11、 _______ 是限定仅在表尾进行插入以及在表头进行删除操作的线性表。

12、 G是一个非连通无向图，共有2边，则该图至少有 ______ 个顶点。

13、 线索二叉树的左线索指向其 ______ ，右线索指向其 ______ 。

14、 在有序表 A[1…20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是 __________ 。

15、 执行顺序查找时，储存方式可以是 _ _ _ _，二分法查找时，要求线性表_ _ _ _ 。

16、 顺序查找用监视哨的作用是 _______。

17、 在单链表中设置头结点的作用是 ________。

18、 对于一个具有 n个结点的二叉树，当它为一棵 _ _ 时具有最

小高度，当它为一棵 _ _ 时，具有最大高度。

19、 从平均时间性能而言， __________排序最佳。

20、 顺序栈用 data[1..n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是_______。

二、 判断题 ( 如果错误请说明理由，每题 1.5 分，共 15 分 ) ：

1、 数据的逻辑结构说明数据元素之间的顺序关系 ,它依赖于计算机的储存结构. ( )

2、 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（ ）

3、 取线性表的第 i个元素的时间同i的大小有关. ( )

4、 二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该树的根结点是那一个，则可以确定这棵二叉树。（ ）

5、 对无序表用二分法查找比顺序查找快。（ ）

6、 通常使用队列来处理函数或过程的调用。（ ）

7、 在 n个结点的无向图中，若边数大于n-1,则该图必存在环路。（ ）

8、 采用二叉链表作存储结构，树的前序遍历和其相应的二叉树

的前序遍历的结果是一样的。（ ）

9、 带权无向图的最小生成树必是唯一的。 （ ）

10、 顺序查找法适用于存储结构为顺序或链接存储的线性表。（ ）

三、 单选题 （每题 1.5 分，共 30 分） ：

1 ． 算法的时间复杂度取决于 （ ）

A．问题的规模 B. 待处理数据的初态 C. A和B

2. 线性表是具有 n个（ ）的有限序列（n>0）。

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．顺序表 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. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表

C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构

8 . 设树 T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）

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

9 . 二叉树的先序遍历和中序遍历如下： 先序遍历： EFHIGJK；中

序遍历: HFIEJKG 。该二叉树根的右子树的根是： （ ）

A、 E B、 F C、 G D、 H

10. 要连通具有n个顶点的有向图，至少需要（ ）条边。

A．n-l B．n C．n+l D．2n

11. 当一个有n个顶点的有向图用邻接矩阵A表示时，顶点Vi的度是（ ）。

A． B． C． D． +

12. 当采用分块查找时，数据的组织方式为 ( )

A．数据分成若干块，每块内数据有序

B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块

D. 数据分成若干块，每块（除最后一块外）中数据个数需相同

13. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为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. 快速

16. 下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。

A． 冒泡 B. 希尔 C. 快速 D. 堆

17. 下列哪一种图的邻接矩阵是对称矩阵？（ ）

A．有向图 B．AOV网 C．无向图 D．AOE网

18. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。

A. O(n) B. O(n+e) C. O(n 2 ) D. O(n 3 )

19. 若串S=‘soft',其子串的数目是（ ）。

A．8 B．11 C．10 D．9

20. 用单链表表示的链式队列的队头在链表的（ ）位置。

A ． 链头 B ． 链尾 C ． 链中 D. 任意位置

四、 应用题 （每题 5分，共25分）

1、 已知如下程序段

for (i= 0;i

x:=x+1 ； { 语句 2} for( j=i;j

y=y+1; { 语句 4} }

语句 1执行的频度为 ；语句2执行的频度为 ；语句3执行的频度为 ；语句4执行的频度为 。

2、 如果两个串含有相等的字符，能否说它们相等？

3、 三维数组 A[1..10,-2..6,2..8]的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间？如果数组元素以行优先的顺

序存贮，设第一个元素的首地址是100，试求元素A[5,0,7] 的存贮首地址。

4、 设 G=(V,E)以邻接表存储，如图所示，试给出该图的深度优先和广度优先遍历序列。

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语言算法，要求插入后链表仍然递增有序。

模拟试题四

《数据结构》期末考试试题

（ 120 分钟） 题号 一 二 三 四 五 总分 题分 20 15 30 25 10 得分

一、 填空题 （每小题 1 分，共 20 分） ：

1、 ___________是数据的基本单位，___________是数据的最小单位。

2、 已知二叉排序树的左右子树均不为空，则 __________上所有结点的值均小于它的根结点值，__________上所有结点的值均大于它的根结点的值。

3、 计算机执行下面的语句时，语句 s的执行次数为 _______ 。

FOR(i=l；i

FOR(j=n;j>=1;j--) s;

4、 设单链表的结点结构为 (data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:________________； _______________;

5、 带头结点的双循环链表 L中只有一个元素结点的条件是：________________ 。

6、 一个栈的输入序列是： 1，2，3则不可能的栈输出序列是 _______ 。

7、 ________又称作先进先出表。

8、 设循环队列用数组 A[0..M-1]表示，队首 、 队尾指针分别是FRONT和TAIL，判定队满的条件为_______________。

9、 一个字符串中 ________ 称为该串的子串

10、 对于一个具有 n个结点的二叉树，当它为一棵 _ _ 时具有最小高度，当它为一棵 _ _ 时，具有最大高度。

11、 数组的存储结构一般采用 _______存储方式。

12、 设某广义表 H=（A，（a,b,c）） ，运用head函数和tail函数求出

广义表H中某元素b的运算式_______________________________。

13、 假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是 ______ 。

14、 已知数组 A[0..9,0..9]的每个元素占3个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[6，7]的地址为_______。

15、 含 4个度为2的结点和5个叶子结点的二叉树，可有 ______ 个度为1的结点。

16、 若以 {4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是 ______ 。

17、 INDEX（‘DATASTRUCTURE'， ‘STR'）= ________ 。

18、 在有 n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要 ______ 条弧。

19、 Prim（普里姆）算法适用于求 ______ 的网的最小生成树； kruskal（克鲁斯卡尔）算法适用于求 ______ 的网的最小生成树。

20、 在哈希函数 H（key）=key%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、 在待排数据基本有序的情况下，快速排序效果最好。 （ ）

8、 在 BST 树 （二叉树排序 树 ）中插入一个新结点，总是插入到叶结点下面。（ ）

9、 拓扑排序的有向图中，最多存在一条环路。（ ）

10、 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 （ ）

三、 单选题 （每题 1.5 分，共 30 分） ：

1 ． 链表不具有的特点是（ ）

A．插入、删除不需要移动元素 B．可随机访问任一元素

C．不必事先估计存储空间 D．所需空间与线性长度成正比

2. 一个栈的输入序列为 123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。

A. 不确定 B. n-i+1 C. i D. n-i

3. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。

A．仅修改队头指针 B. 仅修改队尾指针

C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改

4. 就平均性能而言，目前最好的内排序方法是 ( )排序法。 A.

冒泡 B. 希尔插入 C. 交换 D. 快速

5． 循环队列 A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )。

A. (rear-front+m)%m B. rear-front+1

C. rear-front-1 D. rear-front

6．在双向链表指针p的结点前插入一个指针q的结点操作是（ ）。

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;

7 ． 折半查找的时间复杂性为（ ）

A. O（n 2 ） B. O（n） C. O（nlog n ） D. O（log n ）

8 . 在用邻接表表示图时，拓扑排序算法时间复杂度为( )。

A. O(n) B. O(n＋e) C. O(n*n) D. O(n*n*n)

9 . 设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（ ）

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

A ． 5个 B ． 4个 C ． 3个 D ． 2个

10. 下述二叉树中 ,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。

A．二叉排序树 B．哈夫曼树 C．AVL树 D．堆

11. n个结点的线索二叉树上含有的线索数为（ ）

A．2n B．n－l C．n＋l D．n

12. 串的长度是指（ ）

A．串中所含不同字母的个数 B．串中所含字符的个数

C．串中所含不同字符的个数 D．串中所含非空格字符的个数

13. 栈和队都是（ ）

A．顺序存储的线性结构 B. 链式存储的非线性结构

C. 存取点的线性结构 D. 存取点的非线性结构

14. 循环链表 H的尾结点P的特点是（ ）。

A．P->NEXT == H B．P->NEXT == H->NEXT

C．P == H D．P == H->NEXT

15. 以下数据结构中，哪一个是线性结构（ ）？

A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串

16. 适用于折半查找的表的存储方式及元素排列要求为 ( )

A．链接方式存储，元素无序 B．链接方式存储，元素有序

C．顺序方式存储，元素无序 D．顺序方式存储，元素有序

17. 下列排序算法中，其中（ ）是稳定的。

A. 堆排序，冒泡排序 B. 快速排序，堆排序

C. 直接选择排序，归并排序 D. 归并排序，冒泡排序

18. 下列说法不正确的是（ ）。

A ． 图的遍历是从给定的源点出发每一个顶点仅被访问一次

B ． 图的深度遍历不适用于有向图

C ． 遍历的基本算法有两种：深度遍历和广度遍历

D ． 图的深度遍历是一个递归过程

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}中的字母构成。它们在电文中出现的频度分别为{0.31,0.16,0.10,0.08,0.11,,0.20,0.04},

1) 为这7个字母设计哈夫曼编码；

2）对这7个字母进行等长编码，至少需要几位二进制数？哈夫曼编码比等长编码使电文总长压缩多少？

4、 如图 G：

（ 1）．画出G的邻接表表示图；

（ 2）．根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树。

5、 对于输入关键字序列 48，70，65，33，24，56，12，92建立堆排序的初始堆（小根堆），要求画出主要过程。

五、 编程题 （ 10 分）

1、 写出直接插入排序的类 C 语言算法。

2、 试写出在单链表 La 中删除第 i 个结点的类 C 语言算法。

参

模拟试题一 一．填空题：

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

20 、主关键字

二、 判断题

1、 错；二叉树是有序树，而且二叉树中不一定存在度为二的结点。

2、 错；不一定，比如当待排序列有序时，快速排序蜕变为冒泡排序。

3、 对。

4、 对。

5、 错；广义表的取表尾运算必定是广义表。

6、 错；对排序不是稳定的排序方法。

7、 错；不一定，因为一个连通网的最小生成树并不是唯一的。

8、 错；顺序存储插入和删除运算需要移动大量元素，效率比较低。

9、 对。

10、 错；除了第一个之外，每个都有唯一的直接前驱；除了最后一个之外，每个都有唯一的直接后继。

三、 单选题

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 ）链式存储优点：插入删除不需移动元素仅需改变指针，动态申请空间，易于扩充；

缺点：顺序存取，需要用指针表示逻辑关系。

由上述可见，两种存储结构的优缺点是相反的。

2、 平衡二叉树特点：是二叉排序树，任一子树的左子树和右子树的高度差不超过 1 。

平衡调整方法： LL 调整、 RR 调整、 LR 调整、 RL 调整

3、 先序序列： 5321476

中序序列： 2134567

后序序列： 1243675

4、 表长为 10 ，取 p = 7; 哈希表如下： 地址 0 1 2 3 4 5 6 7 8 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 51 24 95 36

第二趟： [24 45 53] 51 24 95 36

第三趟： [24 45 53 ] 51 24 95 36

第四趟： [24 45 51 53 ] 24 95 36

第五趟： [24 24 45 51 53 ] 95 36

第六趟： [24 24 45 51 53 95] 36

第七趟： [24 24 36 45 51 53 95 ]

五、 编程题

1 、 Status ListInsert_L (LinkList L,datatype x){ p= L;

While(p->next->data < x) // 寻找插入位置

p = p->next; new(s);

s->data = x;

s->next = p->next;

p->next = s;

return OK;

}//ListDelete_L

2 、 int countleaf(BiTree *T){

int n1,n2;

if (T= =NULL) return(0);

else if (T->lchild= =NULL) && (T->rchild= =NULL)

return(1);

else { n1=countleaf (T->lchild);

n2=countleaf (T->rchild);

return( n1+n2);

} }

模拟试题二 一． 填空题：

1 、冒泡 快速

2 、左子树 右子树

3 、 2 3 、 100C

4 、 (rear-front+m)%m

5 、 p->next != null

6 、待排序列关键字随机分布且元素数目多

7 、 n-i+1

8 、 O(n)

9 、顺序

10 、 f->next = p->next;p->next->prior f;f->prior = p;

f;p->next = = 11 、栈

12 、假性上溢

13 、长度相等，相应位置上字符相等

14 、 1340

15 、 n*(i+1)-n*(n+1)/2+(n-j+1) i<=j

16 、串中空格的个数 17 、 9

18 、 完全二叉树 单支树

19 、 prim( 普里姆）

20 、 +1

二、 判断题

1、 错；数据元素是数据的基本单位，数据项是数据的最小单位。

2、 对。

3、 对。

4、 错；两种存储方式各有优点。

5、 对。

6、; 对。

7、 错；应借助队列。

8、 对。

9、 错；应为极小连通子图。

10、 错；折半查找平均性能比顺序查找高，但是比如查找最后一个结点情况则不是这样（顺序查找从后向前找）。

三、 单选题

1 、 D 2 、 C 3 、 C 4 、 D 5 、 C 6 、 C 7 、 B 8 、 C 9 、 D 10 、 B

11 、 D 12 、 B 13 、 D 14 、 C 15 、 D 16 、 D 17 、 B 18 、 B 19 、 A 20 、 C

四、 应用题 1、 答

：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系和操作等的学科。

2、 该二叉树如下图：

3、 构造哈夫曼树如右图：

根据左 0 右 1 ，从根到叶的编码原则可得： a: 01 b:001 c:110 d:0001 e:111 f:10 g:0000

4 、 1 ）深度优先生成树 2 ）广度优先生成树

4、 BST 树如图：

ASL 成功 = （ 1+2*2+3*3+4*2+5*2 ） /10 =16/5

5、 编程题

void StrInsert(char*s,char*t,int pos) {

len1=len2=0; p=s;

while(*p!='\\0') { p++;

len1++; } p=t;

while(*p!='\\0') { p++;

len2++; }

for(p=s+len1;p!=s+pos-1;p--)

*(p+len2)=*p; for(i=0;i

*(s+pos-1+i) = *(t+i); }

模拟试题三 一． 填空题：

1 、 O(1) O(n)

2 、指针

3 、节省存储空间

4 、 head(head(tail(LS)))

5 、 p->next == null

6 、 i(i-1)/2+j-1

7 、 2 k-1 2 k -1 8 、 4

9 、后序

10 、 f->next = p;p-> prior -> next = f; f->prior = p-> prior ;p-> prior = f;

11 、队列 12 、 9

13 、前驱 后继

14 、 1 、 6 、 8 、 11 、 13 、 16 、 18

15 、顺序存储或链式存储 必须为顺序存储

16 、防止下标越界

17 、为了操作上的方便

18 、 完全二叉树 单支树

19 、快速

20 、 data[++top] = x

二、 判断题

1、 错；数据的逻辑结构说明数据元素之间的逻辑关系 , 它不依赖于计算机的储存结构。

2、 对。

3、 错；如果线性表为顺序存储结构时可以随机存取，与 i 值无关。

4、 错；一棵二叉树的前序遍历序列中第一个结点必定是该树的

根结点，不可确定整棵树。

5、 错；无序表不能用二分查找法进行查找。

6、 错；通常使用栈来处理函数或过程的调用。

7、 对。

8、 对。

9、 错；最小生成树不一定是唯一的，比如存在多条权值相同的边的时候。

10、 对。

三、 单选题

1 、 A 2 、 C 3 、 C 4 、 C 5 、 B 6 、 B 7 、 A 8 、 D 9 、 C 10 、 A

11 、 B 12 、 B 13 、 B 14 、 D 15 、 D 16 、 C 17 、 C 18 、 C 19 、 B 20 、 A

四、 应用题

1、 答： n+1 n n(n+1)/2+n n*n

2、 不可以；因为判断两个串是否相等的条件是：两个串长度相等且相应位置上的字符相同。

3、 1 ）（ 10-1+1 ） * （ 6- （ -2 ） +1 ） * （ 8-2+1 ） *4 = 2520 （字节）

2 ）地址为： 100+ （（ 5-1 ） *9*7+ （ 0- （ -2 ）） *7+ （ 7-2 ）） *4=1184

4 、 1 ）深度优先遍历序列： 12345

2 ）广度优先遍历序列： 12435

5、 1 ）二叉树如图： 2 ）森林如下图：

五、 编程题

1 、 int Search_Seq(SSTable* ST,keytype key) {

ST->data[0].key=key;// 设监视哨

for(i = ST->len;ST->data[i].ke

y!=key;i--);// 查找

return i; }

2 、 Status ListInsert_L (LinkList L,datatype x){ p= L;

While(p->next->data < x) // 寻找插入位置

p = p->next;

new(s);// 插入

s->data = x;

s->next = p->next;

p->next = s;

return OK;

}// ListInsert_L

模拟试题四 一、 填空题：

1 、数据元素 数据项

2 、左子树 右子树

3 、 n(n-2)

4 、 py->next = px->next;px->next = py;

5 、 L->next->next = L

6 、 3,1,2

7 、队列

8 、 (TAIL+1)%M = = FRONT

9 、任意个连续字符序列

10 、完全二叉树 单支树

11 、顺序

12 、 head(tail(head(tail(H)))) 13 、 n

14 、 1183

15 、任意

16 、 69 17 、 5 18 、 n

19 、边稠密 边稀疏

20 、小于等于表长的最大质数

二、 判断题

1、 对。

2、 对。

3、 错；在栈的输出序列中如果前面出现了序号大的则后面所有比它序号小的必须是逆序的。

4、 错；队列是一种先进先出的结构。

5、 错；广义表元素可以是空广义表。

6、 错；完全二叉树可以不存在度为 1 的结点。

7、 错；在待排序列基本有序的情况下，快速排序效果比较差。

8、 对。

9、 错；存在环路的有向图不能进行拓扑排序。

10、 对。

三、 单选题

1 、 B 2 、 B 3 、 A 4 、 D 5 、 A 6 、 C 7 、 D 8 、 B 9 、 D

10 、 B

11 、 C 12 、 B 13 、 C 14 、 A 15 、 D 16 、 D 17 、 D 18 、 B 19 、 B 20 、 A

四、 ? 应用题

数据结构指数据元素之间的相互关系；它包含 3 个方面的内容：逻辑结构、物理结构以及在此基础上的运算。

因为 C 第一个出栈，此时 A 、 B 都在栈内，并且 B 在 A 上，所以 B 必在 A 前出栈； D 为第二个出栈，最后可以调节的只有 E ， E 可以在Ｂ、Ａ前出，也可以在Ｂ后Ａ前出，还可以在Ｂ、Ａ后出；可见可能的次序有３种。

１） 构造哈夫曼树如右图：

根据左 0 右 1 ，从根到叶的编码原则可得： a: 01 b:001 c:110 d:0001 e:111 f:10

g:0000

２）等长编码需要三位二进制数；哈夫曼编码的带权平均长度为 2.45 比等长编码压缩大概 18%

4 、 1) 图Ｇ的邻接表如图

2) 深度优先生成树：

建堆如下图： 编程题

1 、 void InsertSort(Splist &L) {

for(i =2;i<= L->length;i++){

L->r[0] = L->r[i];

for(j = i;L->r[j]>L->r[0];j--)

L->r[j+1] = L->r[j];

L->r[j] = L->L->r[0]; } }

2 、 Status ListDelete_L (LinkList L,int i){

p= L;m = 0;

While(mnext) // 寻找位置

{ p= p->next; m++;}

if(p->next!= null){

q = p->next;

p->next = q->next; free(q); }

return OK;

}//ListDelete_L