专升本数据结构试题一

专升本数据结构试题(一)

专业 班级 姓名 学号

一、

填空题(每空2分，共32分)

1．数据结构研究数据的___________、存储结构及数据的运算与实现。

2．在双向循环链表中，在P所指结点之后插入指针f所指结点，其操作为_________________；f->next=P->next；________________________；P->next=f 。

3．在一个长度为n的顺序表中向第i个元素（0＜i≤n+1＝之前插入一个新元素时，需向后移动_______个元素。

4．在等概率情况下，在顺序表中删除一个元素的平均移动次数为___________。 5．栈的特点是__________，栈和队列都是操作受限的线性表。

6．循环队列中队列最大长度为m，front和rear分别为头尾指针，则队列满的条件为__________ ____________________。

7．将中缀表达式A＋（B－C/D）＊E变为后缀表达式为_________________________。 8．空串指_________________________。

9．串A=“date”，B=“are”，C=“basic”，则concat（substring（A，1，3），strDelete（B，2，2），Replace（c，“ic”，“e”））=________________________________

10．出广义表A=（（x，y，z），（a，b，c，d））中原子b的函数是_________________________ 11．nⅹn为对称矩阵，则按行优先原则存储主对角及下三角中元素需___________个存储空间。

若已知Loc(a00)=0，且每个元素占长度为1，则i

___________________。

13．若无向图G为非连通图，则它最少有_____________个连通分量。 14．在有n个顶点的有向图中，每个顶点的度最大可达_____________ 二、

选择题(每题2分，共10分)

1． 下面程序段的时间渐近复杂度为（ ）

I=1； WHILE(I

（A） O（n） （B） O(n*log3n) （C） O(log3n) （D） O(1)

2．线性表的链式存储有利于（ ）运算的实现。

（A） 插入 （B） 读元素 （C） 查找 （D） 定位

.3． 对含有100个记录的表均匀分块检索，若采用单一的顺序检索方式，则可得到最优的ASL为_________。

（A） 10 （B） 11 （C） 9 （D） 8

4．若想在1000个无序记录中，希望用最快速度挑出5个最小元素，则最好用（ ）法排序。

（A） 快速排序 （B） 归并排序 （C） 堆排序 （D） Shell排序 5．采用邻接表存储的图的深度优先搜索遍历算法类似于二叉树的( ) （A） 中序遍历 （B） 先序遍历 （C） 后序遍历 （D） 按层遍历 三、

应用题(共38分)

1．用于通信的电文由abcdefgh八种字符组成，且它们的出现频率依次为0.07，0.19，0.02，

0.06，0.32，0.03，0.21，0.10，则若按权值小者为左孩子构造Huffman树，求各字符的哈夫曼编码，画出哈夫曼树，求带权路径长度。（8分）

2．一组记录的关键字为(19，8，13，26，7，29，33，44)，给定的装填因子为0.8，则用线性探查法解决冲突，利用除留余数法构造散列表，并求出成功查找时的平均查找长度。(10分)

3．用普里姆算法生成最小生成树的过程（6分） 12 v1 v6 6 8 15 13 4 16 v2 v7 v5

12 9 20 10 5 v3 v4

4．写出对下面有向环图进行拓扑排序得到顶点的输出序列的过程，并给出V1到V8的关键路径及路径长度。（8分）

43 v2 v3

6 11 6 38 8

1 12 v1 v4 v5 v8

50 1 24 20 12 v6 v7

5．写出对关键字序列（48，36，65，97，73，15，27，48’）进行快速排序的过程。（6分） 四、

编程题(每小题10分，共20分)

1．试设计将数组A［0??n-1］中所有奇数移到所有偶数之前的算法，要求不另外增加

存储空间，且时间复杂度为O（n）。

2．写出求二叉排序树中关键字的值大于给定值K的结点个数的算法。 #define K 30

typedef int elemtype ; typedef struct node {elemtype key ;

struct node lchild , rchild ; }bitnode , *bitree ; int countnode( t , k ) bitree t ; elemtype k ; {

}

本文来源：https://www.bwwdw.com/article/d8sd.html