统设本科数据结构闭卷考.docx
- 文档编号:8957567
- 上传时间:2023-05-16
- 格式:DOCX
- 页数:57
- 大小:222.08KB
统设本科数据结构闭卷考.docx
《统设本科数据结构闭卷考.docx》由会员分享,可在线阅读,更多相关《统设本科数据结构闭卷考.docx(57页珍藏版)》请在冰点文库上搜索。
统设本科数据结构闭卷考
数据结构(本)期末综合练习
2016年6月
练习一
一、单项选择题
1.下面关于线性表的叙述错误的是()。
A.线性表采用顺序存储必须占用一片连续的存储空间
B.线性表采用链式存储不必占用一片连续的存储空间
C.线性表采用链式存储便于插入和删除操作的实现
D.线性表采用顺序存储便于插入和删除操作的实现
2.数据的存储结构包括数据元素的表示和()。
A.数据处理的方法B.数据元素的类型
C.相关算法D.数据元素间的关系的表示
3.以下数据结构中是非线性结构的是()。
A.队列 B.栈C.线性表 D.二叉树
4.树状结构中数据元素的位置之间存在()的关系。
A.每一个元素都有一个直接前驱和一个直接后继B.一对一
C.多对多D.一对多
5.设有一个长度为18的顺序表,要删除第7个元素需移动元素的个数为()。
A.13B.12C.11D.10
6.设有一个长度为26的顺序表,要插入一个元素,并使它成为新表的第6个元素,需移动元素的个数为()。
A.21B.22C.20D.19
7.两个字符串相等的充要条件是()。
A.两个字符串的长度相等B.同时具备(A)和(C)两个条件
C.两个字符串中对应位置上的字符相等D.以上答案都不对
8.头指针为head的带头结点的单向循环链表,p所指向尾结点,要使该链表成为
不带头结点的单向循环链表,可执行head=head->nex;和()。
A.p=head->nextB.head->next=p
C.head->next=p->nextD.p->next=head;
9.设某链表中最常用的操作是在链表的尾部插入或删除元素,在已知尾指针的条件
下,选用下列()存储方式最节省运算时间。
A.单向链表B.单向循环链表
C.双向链表D.双向循环链表
10.元素111,113,115,117按顺序依次进栈,则该栈的不可能输出序列是()(进栈出栈可以交替进行)。
A.117,115,113,111B.111,113,115,117
C.117,115,111,113D.113,111,117,115
11.元素13,15,19,20顺序依次进栈,则该栈的不可能输出序列是()。
进栈出栈可以交替进行)。
A.20,19,15,13B.13,15,19,20
C.19,13,15,20D.15,13,20,19
12.以下说法正确的是()。
A.栈的特点是先进先出B.栈的特点是先进后出
C.队列的特点是先进后出D.栈和队列的特点都是后进后出
13.设指针q指向单链表中结点A,指针p指向单链表中结点A的后继结点B,则在
表中删除结点B的操作为()。
A.p->next;=q;B.q->next=p->next;
C.p->next=q->next;;D.q->next=p;
14.设有一个20阶的对称矩阵A(第一个元素为a1,1),采用压缩存储的方式,将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始),则矩阵元素a6,2
在一维数组B中的下标是()。
A.21B.17C.28D.23
15.栈和队列的共同特点之一是()。
A.都是先进后出B..都是先进先出
C.没有共同点D.只允许在端点处插入和删除元素
16.设有串p1=”ABADF”,P2=”ABAFD”,P3=”ABADFA”,P4=”ABAF”,以下四个串中最大的是()。
A.p3B.p2C.p1D.p4
17.用链接方式存储的队列,在进行插入运算时()。
A.需修改头指针 B.头、尾指针都需要修改
C.需修改尾指针D.头、尾指针都不需要修改
18.数组a经初始化chara[]=“English”;a[7]中存放的是()。
A.字符串的结束符B.字符h
C.〝h〞D.变量h
19.字符串a1=“AEIJING“,a2=〝AEI“,a3=〝AEFANG〞a4=”AEFI“中最大的是()。
A.a1B.a2
C.a3D.a4
20.设主串为“ABcCDABcdEFaBc”,以下模式串能与主串成功匹配的是()。
A.BcdB.BCdC.ABCD.Abc
21.设有一个20阶的对称矩阵A(第一个元素为a1,1),采用压缩存储的方式,将其
下三角部分以行序为主序存储到一维数组B中(数组下标从1开始),则矩阵中元
素a6,2在一维数组B中的下标是()。
A.23B.17C.21D.18
22.在一棵二叉树中,若编号为i的结点存在左孩子,则左孩子的顺序编号为()。
A.2i+1B.2i-1C.2iD.2i+2
23.以下说法正确的是()。
A.若二叉树中左子树上所有结点的值均小于根结点的值,右子树上所有结点的值
均大于根结点的值。
则该树为二叉排序树。
B.二叉树中任意一个非叶结点的值都大于其左子树上所有结点的值,小于其右子
树上所有结点的值,则该树为二叉排序树。
C.二叉树中任意一个结点的值均大于其左孩子的值,小于其右孩子的值。
则该树
为二叉排序树。
D.前序遍历二叉排序树可得到一个有序序列。
24.如图1所示,若从顶点a出发,按图的广度优先搜索法进行遍历,则可能得
到的一种顶点序列为()。
A.abecdfB.aecbdfC.aebcfdD.aedfcb
25.二叉树的第k层的结点数最多为()。
A.2K-1B.2K+1C.2k-1D.2k-1
26.线性表以()方式存储,能进行折半查找。
A.链接B.顺序C.关键字有序的顺序D.二叉树
27.如图2所示,若从顶点6出发,按深度优先搜索法进行遍历,则可能得到的一种顶点序列为()。
A.6,9,3,2,8,7,4B.6,9,2,3,7,8,4C.6,2,7,9,8,4,3D.6,2,8,7,9,3,4
28.一棵具有38个结点的完全二叉树,最后一层有()个结点。
A.7B.5C.6D.8
29.如图3所示,若从顶点a出发,按广度优先搜索法进行遍历,则可能得
到的一种顶点序列为()。
A.abcfegdB.abcdfgeC.acbfedgD.abcfgde
30.图4的拓扑序列是()。
A.52346B.23645
C.56234D.23564
31.对稀疏矩阵进行压缩存储,可采用三元组表,一个10行8列的稀疏矩阵A,其相应的三元组表共有6个元素,矩阵A共有()个零元素。
A.8B.72
C.74D.10
32.10,6,2,1按顺序依次进栈,该队列的可能输出序列是()。
(进栈出栈可以交替进行)。
A.6,10,1,2B.2,10,6,1
C.6,1,10,1D.1,6,10,2
33.算法的时间复杂度与()有关
A.算法本身B.所使用的计算机
C.算法的程序设计D.数据结构
34.一种逻辑结构在存储时()。
A.只要存储数据元素间的关系B.只能采用一种存储结构
C.可采用不同的存储结构D.只要存储数据元素的值
35.数据结构在计算机内存中的表示是指()。
A.数据元素之间的关系B.数据的存储结构
C.数据元素的类型D.数据的逻辑结构
二、填空题
1.设:
chara[]=“AEIJING“;该字符串在计算机中存储时占________个字节。
2.结构中的数据元素存在多对多的关系称为________结构。
3.结构中的数据元素存在多对多的关系称为________结构。
4.n个元素进行冒泡法排序,第j趟冒泡要进行______次元素间的比较。
5.对稀疏矩阵进行压缩存储,可采用三元组表,一个有8行的稀疏矩阵A共有92个
零元素,其相应的三元组表共有4个元素。
该矩阵A有________列。
6.中序遍历________树可得到一个有序序列。
7.循环链队列中,设front和rear分别为队头和队尾指针,最大存储空间元素为MaxSize,,
采用少用一个存储空间的模式,则判断循环链队列为空的条件是______为真。
8.待排序的序列为8,3,4,1,2,5,9,采用直接选择排序算法,当进行了两趟选择后,结果序列为()。
9.n个元素进行冒泡法排序,第j趟冒泡要进行______次元素间的比较。
10.广义表((a,b),d,e,((i,j),k))的长度是________。
11.设有一棵深度为4的完全二叉树,第四层上有5个结点,该树共有_______个结点。
(根所在结点为第1层)
12.广义表的(c,a,(a,b),d,e,((i,j),k))深度是________。
13.中序遍历一棵________树可得到一个有序序列。
14.对稀疏矩阵进行压缩存储,可采用三元组表,一个有10行10列的稀疏矩阵A共有95个零元素,其相应的三元组表共有个元素。
15.待排序的序列为9,4,5,1,2,6,10,采用直接选择排序算法,当进行了两趟选择后,结果序
列为________。
16.在对一组记录(50,49,97,22,16,73,65,47,88)进行直接插入排序时,当把第7个记录65插入到有序表时,为寻找插入位置需比较_________次。
17.广义表((a,b),d,e,((i,j),k))的长度是________。
18.一棵有5个叶结点的哈夫曼树,该树中总共有_____个结点。
19.广义表的(c,a,(a,b),d,e,((i,j),k))深度是________。
20.设有一棵深度为4的完全二叉树,第四层上有5个结点,该树共有_______个结点。
(根所在结点为第1层)。
21.线性表用________方式存储需要占用连续的存储空间。
22.设有一个长度为40的顺序表,要删除第8个元素需移动元素的个数为_______。
23.线性表用关键字________的顺序方式存储,可以用二分法排序。
24.有以下程序段
chara[]=“English”;
char*p=a;intn=0;
三、综合题
1.
(1)设有数据集合{40,29,7,73,101,4,55,2,81,92,39},依次取集合中各
数据构造一棵二叉排序树。
(2)在上述二叉排序树上进行查找,给出成功查找到元素92的查找路径,其中共经过了
多少次元素间的的比较。
(3)有一个长度为10的有序表,按折半查找对该表进行查找,给出在等概率情况下查
找成功的平均比较次数为。
2.有一个长度为11的有序表(1,2,11,15,24,28,30,56,69,70,80),元素的下标依次为
1,2,3,……,11,按折半查找对该表进行查找。
(1)画出对上述查找表进行折半查找所对应的判定树。
(2)说出成功查找到元素56,,需要依次经过与哪些元素的比较?
(3)说出不成功查找元素72,需要进行元素比较的次数?
3.
(1)以2,3,4,7,8,9作为叶结点的权,构造一棵哈夫曼树,
(2)给出相应权重值叶结点的哈夫曼编码。
(3)一组记录的关键字序列为(47,80,57,39,41,46),利用堆排序的方法建立的
初始堆(堆顶元素是最小元素,以树的形式给出)。
4.
(1)一组记录的关键字序列为(57,90,67,50,51,56),利用堆排序(堆顶元素是
最小元素)的方法建立初始堆(要求以完全二叉树描述)。
(2)对关键字序列(56,51,71,54,46,106)利用快速排序,以第一个关键字为分割元素,
给出经过一次划分后结果。
(3)一组记录的关键字序列为(60,47,80,57,39,41,46,30),利用归并排序的
方法,分别给出(1,1)归并、(2,2)归并、(4,4)归并的结果序列。
四、程序填空题
1.设线性表为(1,3,7,5),以下程序用说明结构变量的方法建立单向链表,并输出
链表中各结点中的数据。
structnode
{intdata;
structnode*next;
};
typedefstructnodeNODE;
#defineNULL0
voidmain()
{NODEa,b,c,d,*head,*p;
a.data=6;
b.data=10;
c.data=16;
d.data=4;/*d是尾结点*/
head=
(1);
a.next=&b;
b.next=&c;
c.next=&d;
(2);/*以上结束建表过程*/
p=head;/*p为工作指针,准备输出链表*/
do
{printf(“%d\n”,(3));
(4);
}while(p!
=NULL);
}
画出按该程序建立的单向链表的示意图,说明程序运行结束后p的指向。
(5)
2.设线性表为(16,20,26,24),以不带头结点的单向链表存储,链表头指针为head,以下程序的功能是输出链表中各结点中的数据域data。
structnode
{intdata;
structnode*next;
};
typedefstructnodeNODE;
#defineNULL0
voidmain()
{NODE*head,*p;
p=head;/*p为工作指针*/
do
{printf(“%d\n”,___
(1)_____);
___
(2)_____;
}while(___(3)_____);
}
3.以下是先序遍历二叉树的递归算法程序,完成空格部分(树结构中左、右指针域分
别为left和right,数据域data为字符型,BT指向根结点)。
voidInorder(structBTreeNode*BT)
{
if(
(1)){
(2);
Inorder(BT->leftt);
Inorder(BT->right);}
}
利用上述程序对右图进行遍历,结果是(3);
4.以下函数为直接选择排序算法,对a[1],a[2],…a[n]中的记录进行直接选择排序,完成
程序中的空格
typedefstruct
{intkey;
……
}NODE;
voidselsort(NODEa[],intn)
{
inti,j,k;
NODEtemp;
for(i=1;i<=___
(1)_____;i++)
{
k=i;
for(j=i+1;j<=
(2)_____;j++)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 本科 数据结构 闭卷