2021年中央电大计算机科学与技术专业数据结构本科试卷

中央电大计算机科学与技术专业

数据构造（本科）试卷7

7月已考

一、选取题（每小题1分，共10分）

1.在一种长度为n顺序表任一位置插入一种新元素渐进时间复杂度为（）。

A.O（n）B.O（n/2）C.0（1）D.O（n2）

2.带头结点单链表first为空鉴定条件是：

A.first==NULL;B.first->link==NULL;

C.first->link==first;D.first!=NULL;

3.当运用大小为n数组顺序存储一种队列时，该队列最大长度为（）o

A.n-2B.n-lC.nD.n+l

4.在系统实现递归调用时需运用递归工作记录保存实际参数值。在传值参数情形，需为相

应形式参数分派空间，以存储实际参数副本;在引用参数情形,需保存实际参数（）,

在被调用程序中可直接操纵实际参数。

A.空间B.副本C.返回地址D.地址

5.在一棵树中，（）没有前驱结点。

A.分支结点B.叶结点C.树根结点D.空结点

6.在一棵二叉树二叉链表中，空指针域数等于非空指针域数加（）o

A.2B.1C.OD.-1

7.对于长度为9有序顺序表，若采用折半搜索，在等概率状况下搜索成功平均搜索长度为

（）值除以%

A.20B.18C.25D.22

8.在有向图中每个顶点度等于该顶点()。

A.入度B.出度

C.入度与出度之和D.入度与出度之差

9.在基于排序码比较排序算法中，()算法最坏状况下时间复杂度不高于O(nlog2n)。

A.起泡排序B.希尔排序C.归并排序D.迅速排序

10.当a值较小时，散列存储普通比其她存储方式具备()查找速度。

A.较慢B.较快C.相似

二、填空题(每小题1分，共10分)

1.二维数组是一种非线性构造，其中每一种数组元素最多有个直接前驱(或直

接后继)。

2.将一种n阶三对角矩阵A三条对角线上元素按行压缩存储于一种一维数组B中,A[0][0]

存储于B⑼中。对于任意给定数组元素B[K],它应是A中第行元素。

3.链表对于数据元素插入和删除不需移动结点，只需变化有关结点______域值。

4.在一种链式枝中，若栈顶指针等于NULL则为。

5.主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用，

它们都需要运用栈保存调用后____地址。

6.在一棵树中，结点没有后继结点。

7.一棵树广义表表达为a(b(c,d(e,f),g(h)),i(j,k(x,y))),结点f层数为。

假定根结点层数为0。

8.在一棵AVL树(高度平衡二叉搜索树)中，每个结点左子树高度与右子树高度之差绝

对值不超过o

9.n（n>0）个顶点无向图最多有条边，至少有条边。

10.在索引存储中，若一种索引项相应数据对象表中一种表项（记录），则称此索引为

索弓I,若相应数据对象表中若干个表项，则称此索引为索引。

三、判断题（每小题1分，共10分）

1.数组是一种复杂数据构造，数组元素之间关系既不是线性也不是树形。

2.链式存储在插入和删除时需要保持物理存储空间顺序分派，不需要保持数据元素之间逻

辑顺序。

3.在用循环单链表表达链式队列中，可以不设队头指针，仅在链尾设立队尾指针、

4.普通递归算法简朴、易懂、容易编写，并且执行效率也高。

5.一种广义表表尾总是一种广义表。

6.当从一种小根堆（最小堆）中删除一种元素时，需要把堆尾元素弥补到堆顶位置，然后

再按条件把它逐级向下调节，直到调节到适当位置为止。

7.对于一棵具备n个结点，其高度为h二叉树，进行任一种版序遍历时间复杂度为0（h）。

8.存储图邻接矩阵中，邻接矩阵大小不但与图顶点个数关于，并且与图边数也关于。

9.直接选取排序是一种稳定排序办法。

10.闭散列法普通比开散列法时间效率更高。

四、运算题(每小题8分，共40分)

1.设有一种10x10对称矩阵A,将其下三角某些按行存储在一种一维数组B中，A[0][0]

存储于B⑼中，那么A凶⑸存储于B中什么位置。

2.这是一种记录单链表中结点值等于给定值x结点数算法，其中while循环有错，请重新

编写出对的while循环。

intcount(ListNode*Ha,ElemTypex)

{〃Ha为不带头结点单链表头指针

intn=0;

while(Ha->link!=NULL){

Ha=Ha->link；

if(Ha->data==x)n++;

)

returnn;

3.已知一棵二叉树前序和中序序列，求该二叉权il后序序列。

前序序列：A,B,C,D,E,F,G,H,I,J

中序序列：C,B,A,E,F,D,I,H,J,G

后序序列：

4.已知一种有序表(15,26,34,39,45,56,58,63,74,76,83,94)顺序存储于

一维数组a[12]中，依照折半搜索过程填写成功搜索下表中所给元素34,56,58,63,

94时比较次数。

24565R6a94

5.设散列表为HT[17],待插入核心码序列为{Jan,Feb,Mar,Apr,May,June,July,

Aug,Sep,Oct,Nov,Dec),散列函数为H(key)=Li/2」，其中,i是核心码第一种字

母在字母表中序号。现采用线性探查法解决冲突。

字母ABCDEFGHIJKLM

序号12345678910111213

字母NOPQRSTUVWXYZ

序号14151617181920212223242526

(1)试画出相应散列表;

(2)计算等概率下搜索成功平均搜索长度；

五、算法分析题(每小题8分，共24分)

1.阅读下列算法，并补充所缺语句

voidpurge_linkst(ListNode*&la){

〃从头指针为la带表头结点有序链表中删除所有值相似多余元素,

〃并释放被删结点空间。

ListNodep,q,t；ElemTypetemp;

p=la->link;

while(p!=NULL){

q=p;

temp=p->data;

p=p->link;

if(p!=NULL&&)p=p->link;

else{

while(p!=NULL&&){

t=p；p=p->link;

deletet;

)

q->link=p;

2.下面给出一种排序算法，它属于数据表类成员函数，其中currentSize是数据表实例当前

长度，Vector[]是存储数据表元素一维数组。

template<classT>

voiddataList<T>:：unknown(){

Ttemp；inti,j,n=currentSize;

for(i=1；i<n；i++)

if(Vector[i].key<Vector[i-l].key){

temp=Vector[iJ；Vectorli]=Vector[i-l];

for(j=i-2；j>=0；j­)

if(temp.key<Vector[j].key)Vector[j+1]=Vector[j];

elsebreak;

Vector[j4-1]=temp;

(1)写出该算法功能。

(2)针对有n个数据对象待排序数据表，在最佳状况下，算法排序码比较次数和对象移

动次数分别是多少？

比较次数：移动次数：

3.已知二叉树中结点类型用BinTreeNode表达，被定义为：

structBinTreeNode{ElemTypedata;BinTreeNode*leftChild,*rightChild;};

其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点指针域。依照

下面函数定义指出函数功能。算法中参数BT指向一棵二叉树树根结点。

BinTreeNode*BinTreeSwopX(BinTreeNode*BT){

if(BT==NULL)returnNULL;

else(

BinTreeNode*pt=newBinTreeNode;

pt->data=BT->data;

pt->rightChild=BinTreeSwopX(BT->leftChild);

pt->lefthild=BinTreeSwopX(BT->righlChild);

returnpt;

六、算法设计题(6分)

已知二叉树中结点类型用BinTreeNode表达，被定义为：

structBTreeNode{chardata;BinTreeNode*leftChild,*rightChild;};

其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点指针域，依照

下面函数声明编写出求一棵二叉树中结点总数算法，该总数值由函数返回。假定参数

BT初始指向这棵二叉树根结点。

intBTreeCount(BinTreeNode*BT);

中央电大计算机科学与技术专业

数据构造（本科）试题参照答案及评分原则7

一、选取题（每小题1分，共10分）

1.A2.B3.B4.D5.C6.A7.C8.C

9.C10.B

二、填空题（每小题1分，共10分）

1.22.L（K+l）/3j3.指针4.空栈

5.返回6.叶子7.38.1

9.n（n-l）/2,010.稠密，稀疏

第9和10小题中有一空错则1分全扣。

三、判断题（每小题1分，共10分）

1.对2.错3.对4.错5.对6.对7.错8.错

9.错10.错

四、运算题（每小题8分，共40分）

1.依照题意，矩阵A中当元素下标I与J满足I>J时，任意元素在一维数组B中

存储位置为1*（1+1）/2+J,因而，A[8][5]在数组B中位置为

8*（8+1）/2+5=41。

2.

while(Ha!=NULL){

if(Ha->data==x)n++;

Ha=Ha->link;

3.后序序列：C,B,F,E,I,J,H,G,D,A

4.判断成果

3456586394

元素值

17AA

比较次数//对1个给1分，全对给8分

5.

H(Jan)=L10/2j=5,成功.H(Feb)=|_6/2」=3,成功.

H(Mar)=L13/2」=6,成功.H(Apr)=Ll/2j=0,成功.

H(May)=L13/2j=6,=7,成功,H(June)=110/2」=5,=6,=7,=8,成功

H(July)=L10/2J=5,=6,=7,=8,=9,成功.

H(Aug)=|_1/2」=0,=1,成功.H(Sep)=L19/2」=9,=10,成功.

H(Oct)=|j5/2」=7,=8,=9,=10,=11,成功.

H(Nov)=114/2」=7,=8,=9,=10,=11,=12.成功.

H(Dec)=14/2」=2,成功.

⑴相应散列表（6分），错一种存储位置扣1分，最多扣6分