一、单项选择题。
1.若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是( )
二00一年下半年全国高等教育自学考试。
数据结构导论试卷。
一、单项选择题。
1.若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是( )
2.在一个具有n个结点的单链表达中查找值为m的某结点，若查找成功，则平均比较（ ）
a． d.(n+1)/2
3．研究数据结构就是研究（ ）
a.数据的逻辑结构b.数据的存储结构。
c.数据的逻辑结构和存储结构 d.数据的逻辑结构，存储结构及其数据在运算上的实现。
4.为了方便地对图状结构的数据进行存取操作，则其数据存储结构宜采用（ ）方式。
a、顺序存储 b、链式存储 c、索引存储 d、散列存储。
5．二维数组a[10……20，5……10]采用行序为主序方式存储，每个数据元素占4个存储单元，且a[10，5]的存储地址是1000，则a[18，9]的地址是（ ）
a、1208b、1212c、1368d、1364
6．设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有（ ）个结点。
a、13b、12c、26d、25
7．下列几种结构中属于树型结构的是（ ）
abcd、8．设无向图g=（v、e）和g’=（v’，e’），如g’为g的生成树，则下面不正确的说法是（ ）
a、g’为g的连通分量b、g’为g的无环子图。
c、g’为g的子图d、g’为g的极小连通子图且v’=v
9．下列说法中不正确的是（ ）
a、无向图的极大连通子图称为连通分量。
b、连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点。
c、图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点。
d、有向图的遍历不可采用广度优先搜索方法。
10．对有序表（18，20，25，34，48，62，74，85）用二分查找法查找85，所需的比较次数为（ ）
a、1次 b、2次 c、3次 d、4次。
11．散列表的平均查找长度（ ）
a、与处理冲突方法有关而与表的长度无关。
b、与处理冲突方法无关而与表的长度有关。
c、与处理冲突方法有关且与表的长度有关。
d、与处理冲突方法无关且与表的长度无关。
12．对isam文件的删除记录时，一般（ ）
a、只需做删除标志b、需移动记录。
c、需改变指针d、一旦删除就需做整理。
13．顺序文件适宜于（ ）
a、直接存取 b、成批处理 c、按关键字存取 d、随机存取。
14．一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用（ ）方法。
a、快速排序 b、堆排序c、插入排序d、二路归并排序。
15．对下列四个序列用快速排序方法进行排序，以序列的第一个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是序列（ ）
a、70，75，82，90，23，16，10，68b、70，75，68，23，10，16，90，82
c、82，75，70，16，10，90，68，23d、23，10，16，70，82，75，68，90
二、填空题。
1．下列程序段的时间复杂性的量级为 0（m*n）
for (i=0; i for (j=0; jt=t+1;
2．索引文件由索引表和主文件两部分组成。
3．在一个不带有头结点的非空单链表中，其结点形式为data | next ，若要在指针q所指结点之后插入一个结点，则需执行下列语句序列：
p=malloc(size); p->data=x; p->next=q->next ; q->next=p;
4．设链栈的栈顶指针为is，栈不空的条件为 is！=null或等价叙述。
5．遍历图的基本方法有深度优先搜索和广度优先搜索。其中，深度优先搜索是一个递归过程。
6．如图所示，设输入元素的顺序为1，2，3，4，5，要在栈s的输出端得到序列43521，则应进行的操作用栈的基本运算表示应为push（s,1），push（s,2），push（s,3），push（s,4），pop(s)， pop(s)，push(s,5), pop(s),pop(s),pop(s)。
7．下图为某树的静态双亲链表表示：
则结点d、e的双亲结点分别为 b、c
8．在下列树中，结点h的祖先为 a、d、g
9．静态查找表的顺序查找算法中，通常采用设置岗哨的方式以确保查找不成功时循环也能终止执行，若给定值为k，表的长度为n，查找表的数据单元用表示，键值用key表示，则在表尾设置岗哨的相应方法描述为
10．对于二叉树的查找，若根结点元素的键值大于被查找元素的键值，则应该在该二叉树的左子树上继续查找。
11．采用二次探测法解决冲突问题，对于键值为k，容量为m的闭散列表，若散列地址为d0，则发生冲突后，其第三个后继散列地址d3为 (d0+22) mod m
12．对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到已排序的有序表时，为寻找其插入位置需比较 3 次。
13．对n个元素进行冒泡排序时，最少的比较次数是 n-1
三．应用题。
1．已知序列（17，18，60，40，7，32，73，65，85），请给出采用冒泡排序法对该序列作升序排序时每一趟的过程。
解：依题意：
初始（17，18，60，40，7，32，73，65，85）
1趟（17，18，40，7，32，60，65，73，85）
2趟（17，18，7，32，40，60，65，73，85）
3趟（17，7，18，32，40，60，65，73，85）
4趟（7，17，18，32，40，60，65，73，85）
5趟（7，17，18，32，40，60，65，73，85）
第5趟元素未交换，则排序结束。
2．如图所示，在栈的输入端有6个元素，顺序为a、b、c、d、e、f。能否在栈的输出端得到序列dcfeba及edbfca？若能，给出栈操作的过程，若不能，简述其理由。
解：（1）能得到序列dcfeba
操作过程如下：
push, push, push, push, pop, pop, push, push, pop, pop, pop, pop
（2）不能得到edbfca
因为要得到e需将a，b，c，d顺序入栈，根据lifo原则，不可能b在c之前出栈。
3．分别写出下列二叉树的先根、中根、后根遍历序列。
解：先根遍历序列：abcdfghe
全国数据结构导论试题
全国2011年10月数据结构导论试题课程 02142 一 单项选择题 本大题共15小题，每小题2分，共30分 1.设栈s和队列q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈s，元素退栈后即进入队列q，若6个元素的出队序列是e2，e4，e3，e6，e5，e1，则栈s的容量至少为 a...
全国数据结构导论试题
全国2013年1月高等教育自学考试。数据结构导论试题课程 02142 一 单项选择题 本大题共15小题，每小题2分，共30分 1.数据的基本单位是。a.数据元素 b.数据项。c.字段 d.域。2.算法的空间复杂度是指。a.算法中输入数据所占用的存储空间的大小。b.算法本身所占用的存储空间的大小。c....
全国数据结构导论试题
全国2012年1月数据结构导论试题课程 02142 一 单项选择题 本大题共15小题，每小题2分，共30分 1.结点按逻辑关系依次排列形成一条 锁链 的数据结构是 a.集合 b.线性结构 c.树形结构 d.图状结构。2.下面算法程序段的时间复杂度为 for int i 0 ifor int j 0 ...