856数据结构与程序设计真题2022.docx

2022年陕西师范大学856数据结构与程序设计真题

一、选择、(3分一道，共10道)

1.在数据结构中，从逻辑上可以把数据结构分成(线性结构和非线性结构)

2.在长度为N的顺序表中，在第j个元素(1=jN+1)之前插入一个新元素时须后移

个元素

3.数组M[m]用来表示一个循环队列，f为当前队列头元素前一个位置，r为队尾元素，假

定队列中元素的个数小于m,计算队列中元素个数公式为

A.(m+f-r)%mB.r-fC.m+r-fD.(m+r-)%m

4关于串的叙述不正确的是

A.串是字符的有限序列B.空串是由空格构成的串

C.模式匹配是串的一种重要运算D.串既可顺序存储，又可链式存储

5.假设以行序为主序存储二维数姐A=array[1..100,1..100],设每个数据元素占2个存储单

元，基地址为10,则LOC[5,5]=

A.808B.818C.1010D.1020

6.对该二叉树进行中序线素化，x的左线索指向的结点和Y结点右线索指向结点分别是

AACB.E,CC.D,FD.C,E

7、哪个算法适合构造一个稠密图G的最小生成树

A.Prim算法、B.Kruskal算法C.Difkstra算法D.Floyd算法

8.对225个元素的顺序表采用分块查找，查找每个元素概率相同，顺序查找每块元素个数

为效率最佳。

9、堆是一种()排序

A.交换B.选择C.插入D.快速

10、字符串“a”在内存中占据字节个数为

A.1B.2C.4

二、填空.(3分一道，共10道)

1、有向图：顶点的入度之和等于出度之和的倍

2、刷除单链表L的第k个元素需找到的结点是

3.F是一个森林，B是由F转换对应的二叉树，F有m个非终结点，B中右指针域为空的

结点有()个

4.栈S进栈顺序为a,b.c,不可能的出栈顺序为

5、串abaabcac的next数组为

6、在带头结点的双向链表L中删除P所指向的结点操作为

7.有栈S,由f1.f2.f3.f4.f5.f6顺序依次进栈，一个元素出栈后进入队列Q,出队顺序为

f2,f4.f3,f6,f5,f1,栈S的容量至少应该是_

8.二叉排序数左子树最大值为max,右子树最小值为min,则max与mim关系为

9、有m个关键字作快速排序，平均算法时间复杂度为

10、有一个二叉树，编号顺序从上至下递增，从左至右递增，根结点编号为1,则编号为i

的结点的父结点的编号是__

三、算法填空。

(1)字符串模式匹配模式串的next函数值

(2)广度优先遍历图的非递归

四、简答题(8分一道，共5道)

1、设表哈希表长度为0-17,H(key)=keymod13,用线性探测法来处理冲突，关键字序列

为{10,24,32,17,31.30,46.47,40,63,49)构建哈希表

2、某树的先序序列为ABEFGCDHJIK,后序序列为EFGBCJHKIDA,请画出该树。

3.对关键字序列(12,2,16,30,28.10.16,20,6,18)进行二路归并排序，写出过程。

4、用Prim算法求无向网的最小生成树

5.通讯字母ABCDEFGH出现频率为7.19.2.6,32.3.21.10,设计最优编码，使电文长

度最短。

五。程序设计。

1.(1)写出函数function的作用.

function(*L)

p=L;

q=Null;

while(p!=Null)

rap-next;

p-nextmq;

q=p;

Per

L=q;

return;

(2)写出算法结果

voidf(intx[],intn)

inta=10;

inti,a[10]={3,5,1,8,2,7,6,4.0,9)

for(=0,i10;i++);

prinf(%d,a[J)

pimtf(“/n*)

inta=10;

for(=0,j10;j++)

printf(%d,a))

pimtf(“/n*)

f(intx[],)(

inttempi

temp=x[i]

x[]=x[J]

x[]=temp

)

2写出二叉树叶子结点个数的非递旧算法、