浙江师范大学计算机考研数据结构试题汇总文档格式.docx
- 文档编号:7186718
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:10
- 大小:60.15KB
浙江师范大学计算机考研数据结构试题汇总文档格式.docx
《浙江师范大学计算机考研数据结构试题汇总文档格式.docx》由会员分享,可在线阅读,更多相关《浙江师范大学计算机考研数据结构试题汇总文档格式.docx(10页珍藏版)》请在冰点文库上搜索。
C.只允许在端点处插入和删除元素
D.没有共同点
3.对线性表进行二分查找时,要求线性表必须______。
A.以顺序方式存储
B.以链接方式存储
C.以顺序方式存储,且结点按关键字有序排序
D.以链接方式存储,且结点按关键字有序排序
4.一组记录的排序码为(47、78、61、33、39、80),则利用堆排序的方法建立的初始堆为______。
A.78、47、61、33、39、80
B.80、78、61、33、39、47
C.80、78、61、47、39、33
D.80、61、78、39、47、33
5.将一棵有50个结点的完全二叉树按层编号,则对编号为25的结点x,该结点______。
A.无左、右孩子
B.有左孩子,无右孩子
C.有右孩子,无左孩子
D.有左、右孩子
6.用快速排序方法对包含有n个关键字的序列进行排序,最坏情况下的时间复杂度为______。
A.O(n)
B.O(log2n)
C.O(nlog2n)
D.O(n2)
7.在最坏的情况下,查找成功时二叉排序树的平均查找长度__(n+1)/2____。
A.小于顺序表的平均查找长度
B.大于顺序表的平均查找长度
C.与顺序表的平均查找长度相同
D.无法与顺序表的平均查找长度比较
8.对序列(22,86,19,49,12,30,65,35,18)进行一趟排序后得到的结果如下:
(18,12,19,22,49,30,65,35,86),则可以认为使用的排序方法是______。
A.选择排序
B.冒泡排序
C.快速排序
D.插入排序
9.在线性表的下列存储结构中,读取元素花费时间最少的是______。
A.顺序表
B.双链表
C.循环链表
D.单链表
10.具有100个结点的二叉树中,若用二叉链表存储,其指针域部分用来指向结点的左、右孩子,其余______个指针域为空。
A.50
B.99
D.101(二叉树中除根结点外都有一个分支进入,共n-1个指针)
11.从逻辑上可以把数据结构划分为______。
A.动态结构和静态结构
B.紧凑结构和非紧凑结构
C.线性结构和非线性结构
D.内部结构和外部结构
12.以下数据结构中属于非线性结构的是______。
A.树
B.字符串
C.队列
D.栈
13.在单链表中,若*P节点不是最后节点,在*P之后插入节点*S,则其操作是______。
A.s->
next=p;
p->
next=s;
B.s->
next=p->
next;
C.s->
p=s;
D.p->
s->
14.栈是一种操作受限的数据结构,其插入和删除必须在______进行。
A.栈顶
B.栈底
C.任意位置
D.指定位置
15.设T为一颗深度为6的二叉树,则T拥有的最多结点数是______。
A.64
B.63
C.32
D.31
16.若用冒泡法对序列(18,14,6,27,8,12,16,52,10,26,47,29,41,24)进行从小到大排序,共要进行的比较次数为______。
A.33
B.45
C.70
D.91
17.算法的时间复杂度取决于______。
A.问题的规模
B.待处理数据的初态
C.计算机的配置
D.A和B
18.对序列(22,86,19,49,12,30,65,35,18)进行一趟排序后得到的结果如下:
A.选择排序
B.希尔排序
C.快速排序
D.插入排序
19.若用一个大小为6的数组来实现循环队列,且当前的rear和front的值分别为0和3,当从队列中删除一个元素,再插入两个元素后,rear和front的值分别为______。
A.1,5
B.2,4
C.4,2
D.5,1(队头front删除,队尾rear插入)
20.对长度为3的顺序表进行搜索,若搜索第一、第二、第三个元素的概率分别为1/2,1/3和1/6,则搜索任一元素的平均搜索长度为______。
A.5/3
B.2
C.7/3
D.4/3(顺序表查找是从最后一个元素顺次向前比较。
最后一个比较1次,最前边比较n次。
ASL=nP1+(n-1)P2+……+2Pn-1+Pn)
三、算法阅读选择题(每小题3分,共30分)
【算法填空1】在画有横线的地方填写合适的内容,并依据以下提供选择的答案,回答
(1)~(5)中的问题。
对顺序存储的有序表进行二分查找的递归算法。
intBinsch(ElemTypeA[],intlow,inthigh,KeyTypeK)
{
if(low<
=high)
{
intmid=
(1)D(low+high)/2;
if(K==A[mid].key)returnmid;
elseif(K<
A[mid].key)return
(2)C.Binsch(A,low,mid-1,K);
else
return(3)B.Binsch(A,mid+1,high,K);
}
Else
return(4)A
1~4问题可供选择的答案:
A.1
B.Binsch(mid+1,high)
C.Binsch(low,mid-1)
D.(low+high)/2
5、试问该递归算法的渐近时间复杂度是(5)。
【算法填空2】在画有横线的地方填写合适的内容,并依据以下提供选择的答案,回答(6)~(10)中的问题。
位数对调:
输入一个三位自然数,把这个数的百位与个位数对调,输出对调后的数。
例如:
输入3位自然数:
234,输出n=432。
//输入的数据为整数
//ProgramThreebit
#include<
stdio.h>
voidmain()
intx,n,a,b,c
printf("
Input3bitnaturedata:
"
scanf("
%d"
&
n)
if(n>
99&
&
n<
1000){
a=(6)
//求百位数n/100
b=(7)
//求十位数(n-a*100)/10
c=(8)
//求个位数n%10
x=(9)
//求新数Xc*100+b*10+a
Number=%d/n"
x);
elseprintf("
Inputerror!
/n"
);
6~9问题可供选择的答案如下:
A.n/100
B.(n-a*100)/10
C.n%10
D.c*100+b*10+a
10、试问该算法的渐近时间复杂度是(10)。
D.O
(1)
四、应用题(每小题6分,共24分)
1.给定二叉树的中序遍历结果为abc,
请画出能得到此中序遍历结果的二叉树的所有形态。
对应的几种先根序:
bac,acb,abc,cba,cab
2.请画出下面无向图的邻接矩阵和邻接表。
1000
1
2
3
^
4
5
3.已知序列{15,18,60,41,6,32,83,75,95}。
请给出采用冒泡排序法对该序列作升序排序时的每一趟的结果。
15,18,41,6,32,60,75,83,95
15,18,6,32,41,60,75,83
15,6,18,32,41,60,75
6,15,18,32,41,60
6,15,18,32,41
intflg=1;
//如果上一趟比较没有交换,终止比较
inti,j;
For(i=0;
i<
n-1&
flg==1;
i++){
flg=0;
for(j=0;
j<
n-1-i;
j++){
if(A[j]>
A[j+1]){t=A[j];
A[j]=A[j+1];
A[j+1]=t;
flg=1;
}
4.有一份电文中共使用五个字符:
a、b、c、d、e,它们的出现频率依次为8、14、10、4、18,请构造相应的哈夫曼树(左子树根结点的权小于等于右子树根结点的权),求出每个字符的哈夫曼编码。
A:
001B:
10C:
01D:
000E:
11
WPL=3*(4+8)+2*(10+14+18)=3*12+2*42=36+84=122
五、算法设计题(21分)
1.以邻接表为存储结构,写出连通图的深度优先搜索算法。
(9分)
//------------邻接表结构------------------
typedefstructArcNode
{
intadjvex;
intweight;
int*info;
structArcNode*nextarc;
}ArcNode;
typedefstructVNode
VertexTypedata;
ArcNode*firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedefstruct
AdjListvertices;
intvexnum,arcnum;
intkind;
}ALGraph;
Intvisited[MaxSize];
//深度优先遍历
voiddfs(ALGraphG,intv)
ArcNode*p;
cout<
<
v<
"
;
visited[v]=1;
p=G.vertices[v].firstarc;
while(p!
=NULL)
if(!
visited[p->
adjvex])
dfs(G,p->
adjvex);
p=p->
nextarc;
}
return;
}
voiddfs1(ALGraphG)
inti;
深度优先遍历:
<
endl;
for(i=0;
i<
G.vexnum;
i++)visited[i]=0;
i++)
if(visited[i]==0)
dfs(G,i);
2.如下图所示,设有两个栈s1和s2共亨同一数组存储空间stack[1m],其中栈s1的栈底设在stack[1]处,而栈s2的栈底设在stack[m]处,请编写栈s1和s2的进栈操作push(i,x)和退栈操作pop(i),其中i=1、2,分别表示栈s1和s2。
要求:
仅当整个空间stack[1m]占满时才产生上溢。
(12分)
typedefElemTypeint;
inttop[3];
//位置0未用
ElemTypestack[m+1];
//位置0未用
initStack(){
top[1]=0;
top[2]=m+1;
intpush(inti,ElemTypex){
if(top[1]+1==top[2])return0;
//栈满
if(i==1){
stack[++top[1]]=x;
elsestack[--top[2]]=x;
return1;
ElemTypepop(inti){
if(top[1]>
0)
returnstack[top[1]--];
else{
if(top[2]!
=m+1)
returnstack[top[2]++];
returnNULL;
//栈空
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 浙江 师范大学 计算机 考研 数据结构 试题 汇总