*注：数据结构测试无答案，前三章为新题型，题号前加粗加下划线的有答案，其余的没有答案，后面几章为旧题，都有答案，复习主要就是看书、看实验题、做题，书上的代码得好好看。
数据结构测试
一．选择题（每题2分，共30分）
1．在数据结构中，从逻辑上可以把数据结构分成（ ）
A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 2．算法分析的目的是（ ）
A．给出数据结构的合理性 B．研究算法中的输入和输出关系 C．分析算法的效率以求改进 D．分析算法的易懂性和健壮性 3．线性表中各元素之间的关系是（ ）关系。
A．层次 B．网状 C．有序 D．集合 4．非空的循环单链表head的尾结点p满足（ ）* A．p->next==NULL B．p->next==head C．p==NULL D．p==head
5．设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为（ ）
A．p->next=p->next->next; C．p=p->next->next;
B．p=p->next; D．p->next=p;
6．某线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。 A．单链表B．仅有头指针的单循环链表 C．双链表D．仅有尾指针的单循环链表 7．栈和队列都是（ ） A．顺序存储的线性结构 C．链接存取的线性结构
B．限定存取的线性结构 D．限定存储的非线性结构
8．一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是（ ） A．edcba B．decba C．dceab D．abcde
9．具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，
1
则判断队满的条件为（ ）
A．rear％n= =front B．front+l=rear C．rear= =front D．(rear+l)％n=front 10．两个字符串相等的条件是（ ）
A．两串的长度相等 B．两串包含的字符相同 C．两串的长度相等，并且两串包含的字符相同 D．两串的长度相等，并且对应位置上的字符相同
11．在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。 A. 4
B. 5
C. 6
D. 7
12．设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）
A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定 13．若下面几个符号串编码集合中，不是前缀编码的是（）。 A．{0,10,110,1111} B．{11,10,001,101,0001} C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc} 14．引入二叉线索树的目的是（） A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一
15．n个结点的线索二叉树上含有的线索数为（） A．2n B．n－l C．n＋l D．n 二．填空题（每空1分，共5分）
1．一个线性表常进行存取操作，很少进行插入和删除操作时，则采用 存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用 存储结构为宜。 2．栈顶的位置是随着 运算而变化的。
3．已知一棵哈夫曼树含有60个叶子结点，则该树中共有______个非叶子结点。 4．高为h（h>0）的满二叉树对应森林的由棵树构成。
三．判断题：在你认为正确的题后（）中填写T，错误的填写F（每题1分，共5分）
2
1．数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ） 2．顺序存储方式只能用于存储线性结构。（ ）
3．线性表的顺序存储结构的优点是存储密度大，且插入、删除运算效率高。（ ） 4．将一棵树转换为二叉树后，根结点没有左子树。（ ） 5．完全二叉树中，若一个结点没有左孩子，则必是叶结点。（ ） 四．简答题（每题2分，共4分）
1． 简述下列算法的功能，并给出队列Q={12，34，25，4，8}在执行下列算法后的状态。
void unknows(SqQueue &Q) {
SqStack S; int k; Initstack(S);
while(!queueempty(Q)) {
Dequeue(Q,k); Push(S,k); }
while(!stackempty(S)) {
Pop(S,k); Enqueue(Q,k); } } 功能：
队列Q的值：
2．假设以二叉链表表示二叉树，其类型定义如下：
typedef struct node { DataType data;
3
struct node * lchild, * rchild; //左右孩子指针 }* BinTree ;
阅读下列算法，并回答问题：
① 已知以T为根指针的二叉树如图所示，写出执行Demo2(T)之后的返回值； ② 简述算法Demo2的功能。 int Demo2( BinTree T) { int d; if ( ! T) return 0;
d = Demo2 ( T - > lchild) +Demo2 ( T - > rchild) ; if (T - > lchild && T - > rchild) return d + 1 ; else return d; }
① 返回值： ② 功能：
五．算法题（每题3分，共6分）
1．设计一个算法，判断链表中数据元素是否是递减的。
2．设某棵二叉树采用二叉链表作为存储，编写一递归算法求其叶结点数。
第一章绪论
一．选择题
1．下面关于算法说法正确的是（ ）。 A．算法最终必须由计算机程序实现
B．为解决某问题的算法同为该问题编写的程序含义是相同的 C．算法的可行性是指指令不能有二义性 D．以上几个都是错误的
2．以下哪一个术语与数据的存储结构无关？（ ）
A．栈B．哈希表 C．线索树 D．循环队列
3．算法复杂度通常是表达算法在最坏情况下所需要的计算量，O(1)的含义是（）。
4
A．算法执行一步就完成 B．算法执行1秒钟就完成
C．算法执行常数步就完成 D．算法执行可变步数就完成 4．数据结构研究的内容是（）。
A．数据的逻辑结构 B．数据的存储结构 C．建立在相应逻辑结构和存储结构上的算法 D．包括以上三个方面
5．一个正确的算法应该具有 5 个特性，除输入、输出特性外，另外 3 个特性是（）。 A．确定性、可行性、有穷性 B．易读性、确定性、有效性 C．有穷性、稳定性、确定性 D．可行性、易读性、有穷性 6．以下关于数据的逻辑结构的叙述中正确的是（）。 A．数据的逻辑结构是数据间关系的描述
B．数据的逻辑结构反映了数据在计算机中的存储方式 C．数据的逻辑结构分为顺序结构和链式结构 D．数据的逻辑结构分为静态结构和动态结构 7．下列时间复杂度中最坏的是（ ）
A．O(1) B．O(n) C．O(log2n） D．O(n2) 8．算法的时间复杂度取决于（ ）。
A．待处理数据的初态 B．问题的规模
C．程序本身所占的空间 D．问题的规模和待处理数据的初态 9．下面说法不正确的是（ ）。
A．算法原地工作的含义是指不需要任何额外的辅助空间
B．在相同规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 C．所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 D．同一个算法，实现语言的级别越高，执行效率就越低
10．在存储数据时，通常不仅要存储各数据元素的值，还要存储（ ）。 A．数据的操作方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存取方法 11．下列关于数据结构的说法中，正确的是（ ）。
A．数据的逻辑结构独立于其存储结构 B．数据的存储结构独立于其逻辑结构
C．数据的逻辑结构唯一决定了其存储结构 D．数据结构仅由其逻辑结构和存储结构决定 12．可以用（ ）定义一个完整的数据结构
A．数据元素 B．数据对象 C．数据关系 D．抽象数据类型 13．某算法的时间复杂度为O(n2)，表明该算法的（ ）
A．问题规模是n2 B．执行的时间等于n2
C．执行时间与n2成正比 D．问题的规模与n2成正比
二．综合应用题
1.有下列运行时间函数：
（1）f1(n)=1000;（2）f2(n)=n2+1000n;（3）f3(n)=3n3+100n2+n+1; 分别写出相应的大O表示的运算时间。
2.下面函数mergesort执行的时间复杂度为多少?假设函数调用为mergesort(1,n)，merge 函数时间复杂度为 O(n)
void mergesort(int i,int j)
5