专升本数据结构试题(二)
专业 班级 姓名 学号
一、
填空题(每空2分，共32分)
1．_______________是数据的不可分割的最小单位。 2． X=9；Y=100； WHILE(Y>0) IF(X>100) {X=X-10；Y- -} ELSE X++；
该程序的时间复杂度为________________。
3．队列的特点是__________，栈和队列都是操作受限的线性表。
4．两栈共享空间时，设向量S的空间长度为m，top1和top2分别是两栈的栈顶指针，则栈2为空的条件为______________________，两栈满的条件是_____________________ 5．储稀疏矩阵的方法有___________ 和十字链表法。
6．对于二维数组Amⅹn，若按行优先原则存储，设每一个元素占c个存储单元，则Loc(aij)＝Loc(a00)+________________________。
7．Head(tail(((a , b) , (c , d))))=__________________。 8．具有65个结点的完全二叉树的深度为___________。
9．T为一棵二叉树，它的叶子结点数为10，则T中左、右孩子具全的结点个数是________。 10．空格串指_________________________。 11．子串的定位操作通常叫做串的______________。
12．设连通图中G的顶点数为 n ，则G的生成树的边数为_____________
13．在有向图G的邻接矩阵A中，若图中不存在弧
14．假定对线性表R[0..59]进行分块检索，共分为10块，每块长度为6，则采用顺序检索方法下的每一个元素的平均检索长度为____________。
15．一个10阶的B－树上，每个非根非叶结点所含关键字个数最多允许为___________ 二、
选择题(每题2分，共10分)
1．P为双向链表中某个结点的指针，则___________。
（A） P->Prior->Next=P->next； （B） P->Prior=P->Next->Prior； （C） P->Next->Prior= P->Prior->Next； （D） P=P->Next->Next->Prior； 2．线性表采用链式存储时，其地址（ ）
（A） 必须是连续的 （B） 一定是不连续的 （C） 连续与否均可 （D） 部分地址必须连续 3．具有n个顶点的完全有向图的边数为 （ ）
（A） n(n-1)/2 （B） n(n-1) （C） n2 （D） n2-1 4．下列哪种排序算法是不稳定的 （ ）
（A） 快速排序 （B） 冒泡排序 （C） 归并排序 （D） 直接插入排序 5．非空单循环链表head的尾结点（由指针P指向）满足（ ）
（A） P->next==Null （B） P==Null （C） P->next==head （D） P==head 三、
应用题(共38分)
1．将下图中的森林转化成对应的二叉树。(6分)
A G K B C D H I L
E F J
2．关键字输入次序如下：(32，50，34，18，10，25，20，38，28)，构造一棵平衡二叉树。(8分) 3．选取哈希函数H(k)=(3k)MOD11，用开放定址法处理冲突d1=H(k)，
di=(di-1+(7*k)+1) (i=2,3,……)，试在0~10的散列地址空间中对关键字序列(22，41，53，46，30，13，01，67)构造哈希表。并求等概率时查找成功的平均查找长度。(8分)
4．写出按Dijkstra算法对下图G求从V1到其他各顶点的最短路径的过程，写出各最短路径及长度。(10分)
43 v2 v3
6 11 6 38 8
1 12 v1 v4 v5 v8
50 1 24 20 12 v6 v7
5．判别以下序列是否为堆？如果不是，则把它调整为堆。（6分） （1） （2） （3） 四、
（100，86，48，73，35，39，42，57，66，21） （15，18，17，25，27，78，28，48）
（12，70，33，65，24，56，48，92，86，33’）
编程题(每小题10分，共20分)
1．某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个带头结点的单链表存入计算机中，链表的每个结点指出同样价格的若干台，现在又新到m台价格为h元的电视机入库，试
编写出仓库电视机链表增加电视机的算法。 链表结点结构：typedef struct node {float price ；/*价格域*/ int num ；/*数量域*/ struct node *next ； }Linklist ；
函数首部：Linklist *insert (head , m , h)
Linklist *head ；int m ；float h ；
2．已知二叉排序树以二叉链表作存储结构，试编写算法按从大到小的的顺序输出二叉排序树的各结点。
typedef int elemtype ;
typedef struct node {elemtype key ;
struct node lchild , rchild ; }bitnode , *bitree ;