数据结构考试题（浙江科技学院）无答案



题序

二
三
四
五
六
七

总分
分









命题：
分

单项选择题题括号填正确答案代号（题15题题2分总计30分）
1数结构研究数（ ）间相互关系
（A）理想结构物理结构 （B）理想结构抽象结构
（C）物理结构逻辑结构 （D）抽象结构逻辑结构
2算法分析两方面（ ）
（A）正确性简单性 （B）读性文档性
（C）数复杂性程序复杂性 （D）时间复杂度空间复杂度
3 头指针head带头结点单链表判定该表空表条件（ ）
（A）headNULL （B）head→nextNULL
（C）head→nexthead （D）headNULL
4队列操作原（ ）
（A）先进先出
（B）进先出
（C）进行插入
（D）进行删
5．设循环队列Q[N]头尾指针FR头指针F总指队列中第元素前位置判断队列空条件（ ）
（A）RF （B）RF
（C）F(R+1)N （D）F(R+1)N
6 设二维数组A[50][60]元素长度4字节行优先序存储基址200元素A[18][25]存储址（ ）
（A）3700　　（B）4376 （C）3900 　（D）4620
7 长度n线性表采序存储结构第i(1（A） O(0) （B） O(1)
（C） O(n) （D） O(n2)
8n顶点连通图少（ ）条边
（A）n1 （B）n （C）n+1 （D）0
9请指出序表{2571014151823354152}中二分法查找关键码17需做（ ）次关键码较
（A）2 （B）3 （C）4 （D）5
10设字符序列{QHCYPAMSRDFX}问新序列{FHCDPAMQRSYX}列排序算法趟扫描结果（ ）
(A)起泡排序
（B）初始步长4shell排序
（C）二路排序
（D）第元素分界元素快速排序
11．设栈输入序列12345 列序列中合法输出序列（ ）
（A）5 1 2 3 4 （B）4 5 1 3 2
（C）3 2 1 5 4 （D）4 3 1 2 5
12．已知图G(VE)中V{V1V2V3V4V5V6V7}E{V3>}G拓扑序列（ ）
(A)V1V3V4V6V2V5V7
(B)V1V3V2V6V4V5V7
(C)V1V3V4V5V2V6V7
(D)V1V2V5V3V4V6V7
13．链表表示线性表优点（ ）
（A）便机存取
（B）便插入删操作
（C）花费存储空间较序存储少
（D）元素物理序逻辑序相
14．图中顶点度数等边数（ ）倍
(A) 12 (B) 1 (C) 2 (D) 4
15．列排序算法中中（ ）稳定
（A）堆排序泡排序
（B）快速排序堆排序
（C）直接选择排序排序
（D）排序泡排序

分

二填空题题中 处填答案（题7题空1分总计12分）
1． 数逻辑结构分____________________线性结构 _________________________________四种
2．面程序段中带画线语句执行次数数量级___________
for (int i0i for (int j0j a[i][j]i*j
3．6数组实现循环队列前rearfront值分03队列中删元素加入两元素rear值___________front值____________
4．组记录排序码(48241853162640)采泡排序法进行排序(升序)第趟排序需进行记录交换次数__________
5．定表（65350387 61908170 512897275 462）筛选法建立初始堆(堆)初始堆表
6．设n结点完全二叉树果左右1开始序编号第i结点（非根结点）双亲结点编号______________右孩子结点编号_____________
7 已知图邻接表存储结构图：顶点1出发深度优先（DFS）遍历输出序列
广度优先（BFS）遍历输出序列









分

三程序填空题题中 处填答案（题3题空3分总计18分）
1 面程序段功实现数x进栈求划线处填正确语句
typedef struct {int s[100] int top} sqstack
void push(sqstack &stackint x)
{
if (stacktopMaxsize1)
printf(overflow)
else
{ ____________________
____________________}
}
2 列算法实现二叉排序树查找关键值k请划线处填正确语句
typedef struct node{int key
struct node *lchild
struct node *rchild}bitree
bitree *bstsearch(bitree *t int k)
{
if (tNULL ) return(0)
else while (tNULL)
if (t>keyk)
_____________
else if (t>key>k)
tt>lchild
else_____________
}
3面程序段功实现快速排序划分算法请划线处填正确语句
typedef struct { int key
InfoType otherinfo}RecType
typedef RecType SeqList[N+1]
int Partition(SeqList Rint iint j)
{ RecType pivotR[i]
while(i {
while(ipivotkey)
j
if(i R[i++]R[j]
while(____________________________________)
i++
if(i _________________________________
}
R[i]pivot
return i }
分

四应题（4题题6分总计24分）
1．设棵二叉树先序中序遍历序列分
先序遍历序列： A B D F C E G H
中序遍历序列： B F D A G E H C
（1）画出棵二叉树
（2）写出棵二叉树序遍历序列


















2设哈希表址空间0…8哈希函数H(k)k7采线性探测散列处理突序列{100202135378}数序次存入哈希表中根求构造哈希表列出插入时较次数求出等概率均查找长度












3应希尔排序算法关键字序列进行排序键值序列{178512 170897 653426154509782}增量序列{531}试写出趟排序结果
















4 图表示区通讯网边表示城市间通讯线路边权表示架设线路花费代价画出普里姆(Prim)算法选择沟通城市总代价省n1条线路
1
3
2
5
4
7
6
8
5
15
3
10
12
2
7
9
6

















分

五算法设计题（2题题8分16分）
1．编写递算法求二叉树深度树定义：
typedef struct BiTNode {
TElemType data
struct BiTNode *lchild *rchild 左右孩子指针
} BiTNode *BiTree

































2．已知两单链表中元素递增序写函数两单链表合成递增序单链表说明算法时间复杂度说明：链表表头单链表结点定义：
typedef struct LNode{ int data struct LNode *next}LN
函数头定义 void MergeList(LN *la LN *lb LN *lc)
lalb分合链表头指针lc合链表头指针


文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档