计算机学院-课件数据结构数据结构题库-数据结构A（物联网算法基础）20

试卷编号：20

信息科学与技术、软件与服务外包、数理学院

各系数据结构A（物联网算法基础）试卷

—-四五六七八总分

学院:成绩

试卷总分：100分答卷时间：1卷分钟

系班级:请考生注意务必将答案写在答题纸上,否则不得分!!!

一、单项选择题（本题有15小题，每小题2分，共30分）

1.数据元素及其关系在计算机存储器内的表示，称为数据的（）。

A.存储结构B,非线性结构

姓名:

C.逻辑结构D.线性结构

2.在一个单链表中，已知q所指向的结点是p所指向结点的前驱结点，若在q和p之

间插入s所指向的结点，则执行（）。

学号:A.s->next=p->next;p->next=s;

B.q->next=s;s->next=p;

C.p->next=s->next;s->next=p;

D.p->next=s;s->next=q;

3.六个元素按6、5、4、3、2、1的顺序进栈，则（）不是合法的出栈序列。

A.453126B.346521

C.543612D.234156

4.假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear,则当前队

列中的元素个数为（）o

A.（rear-front）%m

B.rear-front+1

C.（rear-front+m）%m

D.（front-rear+m）%m

5.设有两个串p和q,其中q是p的子串，求q在p中首次出现的位置的算法称为（）。

A.匹配B.求子串

C.联接D.求串长

6.设有一个1（）阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序

教研室主任

存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地

签字：

址与A⑼⑼的地址之差为（）。

A.10B.28C.55D.19

7.广义表G=（a,（a,（a,（a））））的长度为（）。

A.5B.4C.3D.2

8.若一棵有n个结点的树，则该树中的度之和为（）o

A.n+1B.nC.n-1D.不确定

9.下列叙述正确的是（）o

A.必须把树转换成二叉树后才能进行存储

B.树的后根遍历序列等同于该树对应的二叉树的后序序列

C.己知一棵树的前序遍历序列和中序遍历序列，可以得到该树的后序遍历序列

D.给定一棵树，可以找到唯一的一棵二叉树与之对应

10.下列说法正确的是（）o

A.图的深度遍历适用于有向图

B.有向图的邻接矩阵是对称矩阵

C.邻接多重表适用于有向图的存储

D.图的广度遍历是一个递归过程

11.关键路径是事件结点网络中（）。

A.从源点到汇点的最短路径

B.从源点到汇点的最长路径

C.最长的回路

D.最短的回路

12.下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是（），

A.二分查找B.顺序查找

C.散列查找D.分块查找

13.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A

的左孩子的平衡因子为0,右孩子的平衡因子为1,则应作（）型调整以使其平衡。

A.RLB.LRC.LLD.RR

14.下列排序算法中，第一趟排序结束后，其最大或最小元素一定在其最终位置上的算法

是（）。

A.归并排序B.冒泡排序C.快速排序D,直接插入排序

15.在下列排序算法中，（）算法的时间复杂度与初始顺序无关。

A.直接选择排序B.冒泡排序

C.快速排序D.直接插入排序

二、判断题（本题有10小题，每小题1分，共10分）

1.数据结构包括数据的逻辑结构、存储结构和对数据进行的运算或操作三个方面。

2.链式存储方式比顺序存储方式在插入、删除操作时的效率高。

3.KMP算法的特点是在模式匹配时指示主串的指针不会变小。

4.满二叉树是完全二叉树。

5.一个广义表不能是其自身的一个元素。

6.中序线索二叉树的优点是便于在中序遍历时查找前驱结点和后继结点。

7.即使有向无环图的拓扑序列唯一，也不能唯一确定该图。

8.堆排序是不稳定的。

9.完全二叉树一定是平衡二叉树。

10.二叉树的叶子结点不一定在最下层，但是这些结点的度是一样的。

共（3）页第（1）页未经许可，不得复印试卷/渤海大学考试院/

三、应用题（本题有5小题，每小题6分，共30分）

1.三维数组A[l..10,-2..6,2..8]的每个元素的长度为4个字节，

密（1）试问该数组要占多少个字节的存储空间？

（2）如果数组元素以行优先的顺序存贮，设第一个元素的首地址是100,试求元素

A[5,0,7]的存贮首地址。

学院:

2.已知二叉树的前序和中序遍历序列如下：

前序:ABECDEGIUJ

系班级：中序：EBCDAFHIGJ

试构造出这样的二叉树。并写出其后序遍历序列。

姓名：封

3.一个带权无向图如下图所示，试画出采用普利姆（Prim）算法从vl开始构造出的

一棵最小生成树，要求给出构造过程。

学号:

线

4.已知散列表的地址空间为A[0..Q],散列函数H（k）=kmod11,采用线性探测

法处理冲突。请将下列数据｛25,16,38,47,79,82,51,39,89,151,231｝依次插入到散列

表中，并计算出在等概率情况下查找成功时的平均查找长度。

5.给定初始关键字序列：（26,5,77,1,61,11,59,15,48,19）,按要求回答下面问题:

（1）写出堆排序时初建大根堆的结果。

（2）写出增量为3的这一趟希尔排序结果。

（3）写出以26为基准的第一趟快速排序的结果。

四、程序填空题(本题有2小题，每题6分，共12分)

1.下面程序是将带头结点的单向循环链表逆置的算法，请填空。

typedefintElemType;

typedefstructnode

{ElemTypedata；

structnode*ncxt；

}slink；

voidtum(slink*L)

{slinkQ);

p=L->next;

L->next=L;

while(p!=L)

{q=p;

p=________②；

q->next=L->next;

L->next=@;

}

1

2.以下程序是改进的顺序查找算法，请填空。

/*顺序查找表存储结构*/

typedefintkeytype;

typedefstruct

{keytypekey;/*关键字域*/

/*datatypeothers;*//*其他数据项，可根据需要自行定义*/

JElemType;/*查找表中数据元素类型*/

typedefstruct

{ElemType*elem;/*顺序表基地址切

intlength;/*顺序表长度*/

Jstable;/*查找表类型*/

/*改进的顺序查找算法*/

intseqsearch2(stable①，keytypekey)

{inti;

ST->elem[O].key=key;/*设置监视哨*/

fbr(i=STL>Iength;;i—);

return③：

共（3）页第（2）页未经许可，不得复印试卷/渤海大学考试院/

五、程序设计题（本题有2小题，每小题9分，共18分）

1.二叉树的二叉链表定义如下，假设二叉树中结点的值均为正整数，当输入-1时创

密建空树。写出创建二叉树的算法。

#include"stdio.h'

typcdcfintclcmtypc;

学院:

typedefstructnode

{elemtypedata;

structnode*lchild;

structnode*rchild;

系班级:

)bitnode,*bitree;

2.已知稀疏矩阵的三元组顺序表定义如下，写出从一个二维矩阵创建一个三元组表

姓名:封的算法。

/*定义三元顺序表的最大长度*/

#defineMAXSIZE100

学号:typedefintElemType;

/*三元组的数据类型*/

typedefstruct

{inti;/*行标*/

intj;/*列标*/

ElemTypee;/*非0元素值*/

}tupletype;

线typedefstruct

{intrownum;

intcolnum;

ininznum;

tupletypedatafMAXSIZEl;

}table;

共（3）页第（3）页未经许可，不得复印试卷/渤海大学考试院/

试卷编号：20

信息科学与技术、软件与服务外包、数理学院

密

各系数据结构八（物联网算法基础）试卷答题纸

—-四五六七八总分

:院：成绩

试卷总分：100分答卷时间：1卷分钟

:班级：

一、单项选择题（本题有15小题，每小题2分，共30分）

题号12345678910

答案

1名：封

题号1112131415

答案

学号:二、判断题（本题有1