数据结构模拟考试试卷(1卷)一．判断题（下列各题，正确的请在前面的括号内打√；错误的打×）（√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。
（ㄨ）（2）线性表的链式存储结构优于顺序存储。
（√）（3）将中缀表达式转换成后缀表达式是栈的重要应用。
（×）（4）栈和队列都是顺序存储的线性结构。
（×）（5）“DT”是“DA TA”的子串。
（×）（6）在二叉树中，具有一个子女的父结点，在中序遍历的序列中，它没有后继子女结点。
（×）（7）带权图的最小生成树是唯一的。
（√）（8）散列存储法的基本思想是由关键字的值决定数据的存储地址。
（√）（9）希尔排序是不稳定的排序。
（√）（10）具有n个叶子结点的哈夫曼树共有2n-1个结点。
二．填空题1．线性结构中元素之间存在一对一关系。
2．树形结构和图形结构合称为：非线性结构。
3．顺序表中逻辑上相邻的元素在物理位置上必须相连。
4．在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为O (n) 。
5．同一栈的各元素的类型相同。
6．已知表达式，求它的后缀表达式是栈的典型应用之一。
7．队列在进行出队操作时，首先要判断队列是否为空。
8．设循环队列的头指针front指向队头元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，则队满标志为front==(rear+1)% MAXLEN 。
9．串的链式存储结构简称为链式串。
10．求子串函数SubStr("Today is 30 July,2005",13,4)的结果是：July 。
11．给定如下图所示的二叉树，其层次遍历序列为：ABCEFGH 。
12．将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，该结点右孩子的编号为：2*i+1 。
13．图的遍历有：深度优先搜和 _广度优先搜 __等方法。
14．n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为： _ O（n2）__。
15．二分查找的存储结构仅适用于顺序存储结构，而且关键字有序的。
16．哈希查找是按键值的散列函数值确定散列表中的位置，进行存储或查找。
17．根据被处理的数据在计算机中使用不同的存储设备，排序可分为：内排序和外排序。
18．对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2n)。
19．在双链表中，设prior和next分别表示前一个和下一个的指针域，p指向其中待删除的结点，则删除操作需要执行的命令为：p->prior->next=p->next 。
20．有100个结点的树有99 条边。
三．选择题1．数据结构通常是研究数据的（ A ）及它们之间的相互联系。
A. 存储结构和逻辑结构B. 存储和抽象C. 联系和抽象D. 联系与逻辑2．非线性结构中的每个结点（ D ）A.无直接前趋结点B.无直接后继结点C.只有一个直接前趋结点和一个直接后继结点D．可能有多个直接前趋结点和多个直接后继结点3．用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是（ B ）。
A．当前结点所在地址域B．指针域C．空指针域D．空闲域4．在具有n个结点的单链表中，实现（ A ）的操作，其算法的时间复杂度都是O（n）。
A．遍历链表和求链表的第i个结点B．在地址为P的结点之后插入一个结点C．删除开始结点D．删除地址为P的结点的后继结点5．在栈中，出栈操作的时间复杂度为( A )。
A．O(1) B．O(log2n) C．0(n) D．O(n2)6．带头结点的链栈LS的示意图如下，栈顶元素是（ A ）LSA．A B．B C．C D．D7．以下属于队列的操作有( D )。
A．在队首插入元素 B．删除值最小的元素C．按元素的大小排序 D．判断是否还有元素8．循环队列占用的空间( A )。
A．必须连续B．不必连续C．不能连续D．可以不连续9．串的模式匹配是指（ D ）。
A．判断两个串是否相等B．对两个串比较大小C．找某字符在主串中第一次出现的位置D．找某子串在主串中第一次出现的第一个字符位置10．朴素模式匹配算法在最坏情况下的时间复杂度是( D )。
A．O（m） B．O（n） C．0（m+n） D．0（m*n）11．对于二叉树来说，第K层至多有（ C ）个结点。
A． 2K B．2K-1 C．2K-1 D．2K-1-1 12．线索二叉树是一种（ A ）。
A．物理 B．逻辑 C．逻辑和存储 D．线性13．有n个顶点的有向图的邻接矩阵是用（ B ）数组存储。
A．一维 B．n行n列 C．任意行n列 D．n行任意列14．有n个条边的无向图的邻接表存储法中，链表中结点的个数是（ C ）个。
A．n/2 B．n C．2n D．n*n.15．下列（ C ）不是利用查找表中数据元素的关系进行查找的方法。
A．有序表的查找 B. 平衡二叉树C．散列查找 D．二叉排序树查找16．顺序查找法适合于存储结构为（ B ）的线性表。
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 72 C．16 25 48 35 79 82 23 36 40 72 D．16 25 35 48 79 23 36 40 72 8219．A VL树是一种平衡树的二叉排序树，树中任一结点的（ B ）。
A．左、右子树的高度均相等B．左、右子树高度差的绝对值不超过1 C．左子树的高度均大于右子树的高度D．左子树的高度均小于右子树的高度20．冒泡排序的方法要求被排序的数据（ A ）存储。
A．必须顺序 B．必须链表 C．顺序或链表 D．可以任意四．应用题1．根据二元组关系画出逻辑图形，并指出它们属于何种数据结构。
A=（D，R），其中：D={1，2，3，4，5，6}，R={（1,2）,（1,6）,（2,3）,（2,4）,（3,4）,（3,5）,（3,6）,（4,5）,（5,6）}属于图结构2． 试画出所有三个结点的不同形态的二叉树。
解：三个结点的二叉树：3． 对于算术表达式（A+B*C/D ）*E+F*G ，画出标识符树，并求它们的后缀表达式。
解：后缀表达式：A B C D / * + E * F G * +4． 图G 的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。
解：最小生成树：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡07013070401104031013030801110805．对于给定结点的关键字集合K={1，12，5，8，3，10，7，13，9}，（1）试构造一棵二叉排序树；（2）如何依据此二叉排序树得到D的有序序列。
6．已知数据序列{10，18，4，3，6，12，9，15}，写出二路归并排序的每一趟排序结果。
[10] [18] [4] [3] [6] [12] [9] [15][10 18] [3 4] [6 12] [9 15] 第一趟排序结果[3 4 10 18] [6 9 12 15] 第二趟排序结果第三趟排序结果五．程序填空题（填上适当的表达式、运算符或语句，每空1分，共5分）二叉树按层次遍历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++;}}六．按题目要求，写出运行下列程序的结果(5分)读下列算法，并回答下列问题：（1）采用算法进行排序？（2）算法中R[0]的作用是什么？void insertsort(int R[ ] ){ int i, j;for ( i=2; i<=n; i++ ){ R[ 0 ]=R[ i ];j=i-1;while (R[ 0 ]< R[ j ]){ R[j+1]=R[j]; j- -; }R[ j+1 ]=R[0];}}解：（1）直接插入法（2）监视哨（或哨兵）七．程序设计题链栈的存储结构和栈顶指针定义如下：#define MAXLEN 100typedef struct stacknode // 定义栈的存储结构{int data;struct stacknode *next;}stacknode;typedef struct{ stacknode *top; // 定义栈顶的指针}linkstack;试写出把十进数转换为二进制数的程序。
解：void Conversion(int n) // 栈的应用：二—十进制转换{ linkstack s;int x;s.top=NULL; // 置栈空do{ x=n%2; // 取余数n=n/2; // 取新的商stacknode *p=new stacknode ; // 申请新结点p->next=s.top ; // 修改栈顶指针s.top=p;s.top->data=x ; // 余数入栈}while (n);cout<< " 转换后的二进制数值为：";while (s.top) // 出栈处理{ cout<< s.top->data ;stacknode *p=s.top;s.top= s.top->next ;delete p ; // 出栈一个余数，收回一个结}}。