数据结构模拟考试试卷(2卷)一．判断题（下列各题，正确的请在前面的括号内打√；错误的打×）（√）1.数据的逻辑结构是独立于计算机的。
（×）2.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的存储结构。
（√）3.栈的特点是“后进先出”。
（√）4.判断顺序队列为空的标准是头指针和尾指针均指向同一个结点。
（×）5.串的堆分配存储是一种静态存储结构。
（×）6.完全二叉树一定是满二查树。
（×）7.邻接表只能用于有向图的存储。
（×）8.选择好的哈希函数就可以避免冲突的发生。
n)。
（√）9.对于n个记录的集合进行归并排序，所需的平均时间为O (nlog2（×）10.对于满足二分查找和分块查找条件的文件而言，无论它存放在何种介质上，均能进行顺序查找，折半查找和分块查找。
二．填空题1．数据结构是一门研究非数值计算程序设计中计算机的操作对象以及它们之间的关系和运算的学科。
2．数据的存储结构形式包括：顺序存储、链式存储、散列存储、索引存储。
3．在线性表的顺序存储中，元素之间的逻辑关系是通过相邻位置决定的。
4．在双向链表中，每个结点都有两个指针域，它们一个指向其前趋结点，另一个指向其后继结点。
5．在有n个元素的栈中，出栈操作的时间复杂度为 O（1）。
6．在栈结构中，允许插入、删除的一端称为栈顶。
7．对于队列，只能在队首删除元素。
8．循环队列SQ经过InitQueue (SQ)，SQ->front等于0 。
9．空格串的长度等于空格的个数。
10．设目标T="abccdcdccbaa"，模式P="cdcc"，则第 6 次匹配成功。
11．采用二叉链表存储的n个结点的二叉树，一共有2n 个指针域。
12．给定如下图所示的二叉树，其前序遍历序列为：ABEFHCG 。
Array13．图的逆邻接表存储结构只适用于 __有向____图。
14．一个图的生成树的顶点是图的 _ 全部____顶点。
15．快速排序是对冒泡排序的一种改进。
16．在哈希函数H(key)=key % P中，P一般应取质数。
17．大多数排序算法都有两个基本的操作：比较和移动。
18．在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第19个记录60插入到有序表时，为寻找插入位置至少需比较 6 次。
19．一个连通图有 1 个连通分量。
20．已知二叉树有50个叶子结点，则二叉树的总结点树至少是99 。
三．选择题1．执行下列语句的时间复杂度为：（ B ）。
s=0;for (i=1;i<=n; i++)s=s+i;A. O（1）B. O（n）C. O（n2）D. O（n3）2．数据结构中，在逻辑上可以把数据结构分成：（ C ）。
A. 动态结构和静态结构B. 紧凑结构和非紧凑结构C. 线性结构和非线性结构D. 内部结构和外部结构3．向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ B ）个元素。
A．8 B．63.5 C．63 D．74．用链表存储的线性表，其优点是（ C ）。
A．便于随机存取B．花费的存储空间比顺序表少C．便于插入和删除D．数据元素的物理顺序与逻辑顺序相同5．在栈顶一端可进行（ D ）操作。
A．插入 B．删除 C．进栈D．插入和删除6．从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列 ( D )命令。
A．x=top;top=top->next; B．top=top->next;x=top->data;C．x=top->data; D．x=top->data;top=top->next; 7．若进队的序列为：A，B，C，D，则出队的序列是（ C ）。
A．B，C，D，A B．A，C，B，DC．A，B，C，D D．C，B，D，A8．从一个顺序循环队列删除一个元素时，首先需要做的操作是（ B ）。
A．队头指针减1 B．取出队头指针所指的元素C．队头指针加1 D．取出队尾指针所指的元素9．串是（ D ）。
A. 不少于一个字母的序列B．任意个字符的序列C. 不少于一个字母的序列D．有限个字符的序列10．若串S="SOFTWARE"，其子串的数目是：（ C ）。
A．35 B．36 C．37 D．388+7+6+5+4+3+2+1+1=3711．根据二叉树的定义，具有3个结点的二叉树有（ C ）种树型。
A．3 B．4 C．5 D．612．如右图所示的二叉树，先序遍历的序列是（A． A、B、C、D、E、F、G 、H、IB． A、B、D、H、I、E、C、F、GC． H、D、I、B、E、A、F、C、GD． H、I、D、E、B、F、G、C、A13．有8个结点的无向连通图最少有( C )条边。
A． 5 B. 6 C. 7 D. 614．任何一个无向连通图的最小生成树( A )。
A．只有一棵 B．一棵或多棵 C．一定有多棵 D．可能不存在15．平衡二叉树的各结点左右子树深度之差不能为（ D ）。
A．-1 B．0 C．1 D．216．静态查找的全部运算是（ D ）。
A．建表 B. 建表和查找C．查找和读表元素 D．建表、查表和读表元素17．排序方法中，从无序序列中选择关键字最小的记录，将其与无序区（初始为空）的第一个记录交换的排序方法，称为: ( D )。
A．希尔排序 B．归并排序 C．插入排序 D. 选择排序18．一组记录的排序码为(25，48，16，35，79，82，23，40，36，72)，其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为：（ A ）。
A，16 25 35 48 23 40 79 82 36 72 B．16 25 35 48 79 82 23 36 40 72C．16 25 48 35 79 82 23 36 40 72 D．16 25 35 48 79 23 36 40 72 82 19．有序表是（ A ）的查找表。
A．结点按键值有序排列 B. 顺序存储C．二叉排序树 D．散列存储20．将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为49的结点的右孩子编号为（ B ）。
A．98 B．99 C．50 D．100四．应用题1．根据二元组关系画出逻辑图形，并指出它们属于何种数据结构。
C=（D，R），其中：D={1，2，3，4，5，6}，R={（1,2）,（2,3）,（2,4）,（3,4）, （3,5）,（3,6）,（4,5）,（4,6）}解：属于图结构2． 某二叉树的结点数据采用顺序存储，其结构如下：（1）画出该二叉树（3分）（2）写出按层次遍历的结点序列（2分） 解： （1）（2）层次遍历的结点序列：E A F D H C G I B3． 已知一棵树的层次遍历的序列为：ABCDEFGHIJ ，中序遍历的序列为：DBGEHJACIF ，请画出该二叉树，并写出它的后序遍历的序列。
解：后序遍历的序列：D G J H E B I F C A 4． 根据如下有向图，画出邻接矩阵和邻接表。
解（1）邻接矩阵 1 2 3 4 5⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛0100000001100000100010110543215． 对于给定结点的关键字集合K={34，76，45，18，26，54，92，38}， （1）试构造一棵二叉排序树；（2）求等概率情况下的平均查找长度ASL 。
解：（1）构造二叉排序树（2）ASL=（1*1+2*2+3*3+4*2）/ 8 =2.75 （或=11/4）6． 已知数据序列{10，18，14，13，16，12，11，9，15，08}，写出希尔排序每一趟（设d=5、2、1）排序的结果。
① ②③④⑤解： 10 18 14 13 16 12 11 09 15 08 d=510 11 09 13 08 12 18 14 15 16 d=208 11 09 12 1013 15 14 18 16d=1 08 09 10 11 12 13 14 15 16 18五．程序填空题（填上适当的表达式、运算符或语句，每空1分，共5分）以二叉链表为存储结构，试完成求二叉树深度的程序填空typedef struct BT{ datatype data; // 定义结点 BT *lchild; BT *rchild; }BT;int TreeDepth(BT *T) // 求树深度 { i nt ldep,rdep; if( T==NULL ) return 0; else{ ldep= TreeDepth(T->lchild) ; rdep= TreeDepth(T->rchild) ; if(ldep>rdep)return ldep+1 ; elsereturn rdep+1 ; }}六．按题目要求，写出运行下列程序的结果二叉树的结构如图所示，试写出执行下列算法后的输出结果： 。
（用大写的英文字母表示，字母之间不要任何间隔符号，最后一个字母后面也不要间隔符号）typedef struct BT{ datatype data; // 定义结点 BT *lchild;BT *rchild; }BT;void Levelorder(BT *T) { i nt i,j;BT *q[100],*p; p=T;if (p!=NULL){ i=1;q[i]=p;j=2; }while (i!=j){ p=q[i]; cout<<p->data ;if (p->lchild!=NULL){ q[j]=p->lchild; j++;}if (p->rchild!=NULL){ q[j]=p->rchild; j++; }i++;}}解：ABDCFGE 层次遍历七．程序设计题设待排序的文件用单链表做存储结构，头指针为head，写出其选择排序算法。
void select ( lklist head ){ p=head;while ( p!=NULL ){ s=p;q=p->next;while ( q!=NULL ){ if ( q->key < s->key )s=q;q=q->net;}if ( s!=p ){ t=p->key;p->key=s->key;s->key=t;}}p=p->next;}。