广州招生网
当前位置: > 短期培训 > 专插本 > 试题资料 >

广东专插本2017年专插本计算机科学与技术专业课数据结构试卷(

2018-01-06 15:48 感兴趣的有:
广东专插本2017年本科插班生考试试卷
 计算机科学与技术 专业  数据结构 试卷(A卷)
 

题号 总分 评卷人
得分                
 
得分 评卷人
   
一、单项选择题(每题2分,共30分)
 
 
1. 对线性表,在下列哪种情况下应当采用链表表示?(     )
 A. 经常需要随机地存取元素      B. 经常需要进行插入和删除操作
  C. 表中元素需要占据一片连续的存储空间  D. 表中元素的个数不变
2.  一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是(    )。
   A. 2 3         B. 3 2 1        C. 3 1 2 D. 1 2 3
3.程序段s=i=0;do {i=i+1; s=s+i;}while(i<=n);的时间复杂度为(  )。
A. O(n) B. O(nlog2n) C.O(n2) D.O(n3/2)
4.一个非空广义表的表头(    )。
   A.不可能是子表                B.只能是子表
   C.只能是原子                  D.可以是子表或原子
5.设数组data[m]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出队操作后其头指针front值为(     )。
   A. front=front+1                 B. front=(front+1)%(m-1)
   C. front=(front-1)%m             D. front=(front+1)%m
6.在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行(    )。
   A. s→link=p→link;   p→link=s;   B. p→link=s;   s→link=q;
   C. q →link=s;   s→link =p;       D. p→link=s→link;   s→link=p;
7.设有一个二维数组A[m][n],假设A[0][0]存放位置在644(10)A[2][2]存放位置在676(10),每个元素占一个空间,问A[3][3](10)存放在什么位置?脚注(10)表示用10进制表示(    )。
   A. 696        B. 692       C.688       D. 678
8.用某种排序方法对关键字序列(25,84,21,47,15,27,68,35,20)进行排序时,序列的变化情况如下:
        20,15,21,25,47,27,68,35,84
        15,20,21,25,35,27,47,68,84
        15,20,21,25,27,35,47,68,84
   则所采用的排序方法是(   )。
  A.选择排序     B.希尔排序     C.归并排序    D.快速排序
9.组成数据的基本单位是(   )。 
A. 数据项 B.数据类型 C.数据元素 D.数据变量
10.数组的逻辑结构不同于下列(   )的逻辑结构。
A. 树 B. 栈  C. 队列 D. 线性表
11.根据二叉树的定义可知二叉树共有(    )种不同的形态。
A.4 B. 5 C. 6 D. 7
12.设一条单链表的头指针变量为head且该链表没有头结点,则其判空条件是(   )。
A. head==0   B. head->next==0   C. head->next==head  D. head!=0
13.设用邻接矩阵A表示有向图G的存储结构,则有向图G中顶点i的入度为(   )。
A.第i行非0元素的个数之和 B. 第i列非0元素的个数之和
C.第i行0元素的个数之和    D. 第i列0元素的个数之和
14.设无向图G中有n个顶点,则该无向图的最小生成树上有( )条边。
A. 2n B. 2n-1 C. n-1 D. n
15.由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为(    )
 A. 24        B. 48          C. 53           D. 71
 

得分 评卷人
   
二、填空题(每空2分,共20分)
 
 
1.数据的物理结构主要包括_____________和______________两种情况。
2.设某棵二叉树中度数为0的结点数为N0,度数为1的结点数为N1,则该二叉树中度数为2的结点数为_________;若采用二叉链表作为该二叉树的存储结构,则该二叉树中共有_______个空指针域。
3. 设顺序线性表中有n个数据元素,则第i个位置上插入一个数据元素需要移动表中_______个数据元素;删除第i个位置上的数据元素需要移动表中_______个元素。
4.设某无向图G的邻接表为


,则从顶点V1开始的深度优先遍历序列为__________      _;广度优先遍历序列为____         ____。
5. 设有一组初始关键字序列为(24,35,12,27,18,26),则第3趟直接插入排序结束后的结果的是______________________  ________; 
 设有一组初始关键字序列为(24,35,12,27,18,26),则第3趟简单选择排序结束后的结果的是__________________________________。
 

得分 评卷人
   
三、判断题(对的划√,错的划×。每小题1分,共10分)
 
(     )1.线性表中的所有元素都有一个前驱元素和后继元素。 
(     )2.不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑“溢出”情况。
(     )3.对连通图进行深度优先遍历可以访问到该图中的所有顶点。
(     )4.由树转化成二叉树,该二叉树的右子树不一定为空。
(     )5.如果某个有向图的邻接表中第i条单链表为空,则第i个顶点的出度为零。
(     )6..有向图的邻接表和逆邻接表中表结点的个数不一定相等。
(     )7.不论线性表采用顺序存储结构还是链式存储结构,删除值为X的结点的时间复杂度均为O(n)。
(     )8.关键路径是AOE网中源点到汇点的最短路径。
(     )9.图的深度优先遍历算法中需要设置一个标志数组,以便区分图中的每个顶点是否被访问过。
(     )10.用邻接矩阵作为图的存储结构时,则其所占用的存储空间与图中顶点数无关而与图中边数有关。
 

得分 评卷人
   
四、程序填空题(每个空2分,共10分)
 
 
1. 下面程序段的功能是实现一趟快速排序,请在下划线处填上正确的语句。
 struct record {int key;datatype others;};
void quickpass(struct record r[], int s, int t, int &i)
{ int j=t; struct record x=r[s]; i=s;
  while(i<j)
{while (i<j && r[j].key>x.key) j=j-1;  if (i<j) {r[i]=r[j];i=i+1;}
    while (____________________) i=i+1;  if (i<j) {r[j]=r[i];j=j-1;}
  }
  _________________;
}
 
2. 如下为二分查找的非递归算法,试将其填写完整。
Int Binsch(ElemType A[ ],int n,KeyType K)
{
int low=0;
int high=n-1;
while (low<=high)
{
int mid=_______________________________;
if (K==A[mid].key)  return mid;    //查找成功,返回元素的下标
   else if (K<[mid].key)
_________________________;   //在左子表上继续查找
       else __________________;    //在右子表上继续查找
}
return -1;      //查找失败,返回-1
}
 

得分 评卷人
   
五、分析简答题(第一题8分,其余各题6分,共20分)
 
1.(8分)已知一个图的顶点集V和边集E分别为:
        V={1,2,3,4,5,6,7};        E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};
用克鲁斯卡尔算法(Kruskal)得到最小生成树,试写出在最小生成树中依次得到的各条边。
 
 
2. (6分)设某棵二叉树的中序遍历序列为DBEAC,前序遍历序列为ABDEC,试写出这棵二叉树的后序遍历结果并画出这颗二叉树。
 
  
3.(6分)一个线性表为B=(12,23,45,57,20,03,78,31,15,36),设散列表为HT[0..12],散列函数为H(key)= key % 13并用线性探查法解决冲突,请画出散列表,并计算等概率情况下查找成功的平均查找长度。  
 

得分 评卷人
   
六、 算法设计题(10分)
 
 
设有一线性表(a1, a2,…,an-1)用单链表存储,写算法实现将其就地逆置的操作。(“就地”是指辅助空间应为O(1)) 


分享到:

报名方式

1.直接来我校参观、报名。报名时带好身份证及正反面复印件2张、1寸蓝底彩照4张2寸蓝底彩照4张 。 (专升本在校生由学校开具证明,毕业生应交毕业证复印件)

2.学生选择网上或电话报名,学员可以电话、QQ、电子邮件报名或者索取招生简章,在指定时间内来校报到入学。

3.业余自考学生准备好个人资料和第一年学费,直接过来学校报名。

4.电话:020-85517608 或 13316047870 李老师(微信同号)

5.QQ: 点击这里给我发消息

6.广州招生网在线报名地址:点击进入网上报名系统

7.报名地址:广州天河中山大道西8号天河商贸大厦2203招生办(地铁3号线岗顶站;公交站师大暨大站)


快速报名及预约看学校

姓名:
电话:
QQ:
备注留言:
 

(特别提醒:我校没有在各车站路口设立接待点,请广大考生自行来校,严防路人以指路带领为名上当受骗,中途勿受陌生人接待,以免误导,造成不必要的财产损失。)

暨南大学自学考试招生海报