2013数据结构复习题
一、判断题
1、一个图的广度优先遍历序列是唯一的，这种说法（F ）。 可有多种
2、在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是哈希查找，这种说法（ T ）。
3、在二叉树中，指针P所指结点为叶子结点的条件是P->lchild==NULL, 这种说法 ( F )
4、完全二叉树一定是满二叉树（ F）
满二叉树一定是一棵完全二叉树，反之完全二叉树不一定是一棵满二叉树。满二叉树的叶子结点全都在最底层，而完全二叉树的叶子结点可以分布在最下面两层。
6、邻接表只能用于有向图的存贮（F ）
7、连通图一定是完全图，反之亦然。这个断言是（F ）
8. 二叉树的左右子树的位置总是可以交换的，这个断言是（ F）
二、选择题
1、若对线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（ A ）最节省时间。
A．顺序表 B.带头结点的双循环链表 B.单链表 C.带尾结点的单循环链表 2、带头结点的单链表L为空的判定条件是(C)。 A．L==NULL B.L->next==NULL C. L->next==L D.L!=NULL 3、栈和队列的共同点是(C ).
A．都是先进后出 B. 都是先进先出
C.只允许在端点处插入和删除元素 D.没有共同点
4、一组记录的关键码为(45，75，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果是（C）。 A．38，40，45，56，75，84
B．40，38，45，75，56，84 C．40，38，45，56，75，84 D．40，38，45，84，56，75
5、一个有n 个顶点的有向图最多有 （ B ）条边。
A． n B. n*(n-1) C. n*(n-1)/2 D. 2*n
6、采用顺序查找方法查找长度为N的线性表时，每个元素的平均查找长度为（C ）
A．N B.N/2 C.(N+1)/n D.(N-1)/2 7.对线性表进行二分查找时，要求线性表必须(C )。 A．以顺序方式存储 B．以链接方式存储
C．以顺序方式存储，且结点按关键字有序排序
D．以链接方式存储，且结点按关键字有序排序
8. 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是(D)。
A．n B．(n一1) 2 C．n-1 D．n * n
9. 设有两个串s和t，求t在s中首次出现的位置的运算称作(B )。 A．连接 B．模式匹配 C．求子串 D．求串长
10. 一个数组第一个元素的存储地址是100，每个元素的长度为4．则第5个元素的地址 是（B ）。
A．110 B.116 C．100 D．120 11．深度为K的二叉树最多有（D）结点。
A．N B．N+1 C．2N D．2k－1
12．在一个单链表中，若p指针指向结点不是最后结点，在p指针所指结点之后插入s指针所指结点，则执行操作（B）。 A．s-〉next＝p；p->next＝s；
B．s->next＝p->next；p->next＝s； C．s->next＝p->next；p＝s； D．p->next＝s；s->next＝p； 13.顺序栈判空的条件是（ A ）。
A. top==0 B. top==1 C.top==-1 D.top==m 14、元素A、B、C、D依次进顺序栈后，栈顶元素是（D ），栈底元素是（A）。 A． A B. C C. B D. D
15、深度为5（K）的二叉树至多有（C ）个结点。最少k个，最多2^k-1个 A． 16 B. 32 C. 31 D. 10 三.问答题
1、一个好的算法应该达到什么标准？ （1）执行算法所耗费的时间短 （2）执行算法所占用的内存开销小
（3）算法应易于理解，易于编码，易于调试等。
2、对N个顶点的无向图G 采用邻接矩阵表示，如何判别下列有关问题：P141 A. 图中有多少条边？矩阵中1的个数的一半为图中边的数目
B. 任意两个顶点i 和 j是否有边相连？看矩阵中第i行第J列的值是否为
1
C. 任意一个顶点的度是多少？第i行或第i列1的个数为顶点i的度 3、 串和一般线性表有何区别？
串：是一种线性表，是一种数据类型受到限制（只能为字符型）的线性表。 一般线性表：数据的类型可以根据具体情况而定。 4、线性表、栈、队列有什么异同 ？
N（n>=0）个数据元素a1,a2.......an组成的有限序列。
栈是限制线性表中元素的插入和删除只能在线性表的一端进行的一种特殊线性表。
仅允许在一端进行插入，另一端进行删除的线性表，称为队伍
5、 按照二叉树的定义，具有3个结点的二叉树有几种形态。 259 6、 一个队列的入队序列是1，2，3，4，则队列的输出序列是什么？ 1，2，3，4
7、算法有哪些特征？ 1.输入 2.输出 3.有穷性 4.确定性 5.可行性 四.应用题
1.课本134页，第6－6题、第 6－9 题 2.课本第112页对图6－11二叉树遍历. 3.181页7－6题，写出单源最短路径。
4.180页7－2题，写出深度、广度序列。 第148页对图7－13进行深度、广度遍历。
5． 140页 邻接矩阵。 6．144页 邻接表。 7．158页 最小生成树。
8．49页 中缀表达式转换为后缀和前缀表达式。 五、填空题： 1、．栈的特点是先进后出 ，队列的特点是 先进先出 。
3、算法分析的二个重要标准是 时间的复杂度和空间复杂度 。 算法的特性是 输入，输出，有穷性，确定性，可行性 。
4、对非空二叉树的中序遍历中，根结点的左边只有 只有左子树上的所有结点
六、程序题
二分查找算法。
int binsearch(node R[n+1],elemtype k) {
int low=1,high=n; while(low<=high) {
int mid=(low+high)/2; if(R[mid].key==k) return mid;
else if(R[mid].key>k) high=mid-1; else low=mid+1; }
return 0; }
设已建立了单链表，写出删除单链表中给定元素X 的算法。 void link::dele(link *head, elemtype x) {
link *p,*q; q=head; p=head->next;
while(p!=NULL)&&(p->data!=x) {
q=p;
p=p->next; }
if(p==NULL) cout<<”要删除的结点不存在”; else {
q->next=p->next; delete(p); } }
写出快速排序算法。
void quicksort(elemtype R[],int left,int right) {
int i=left, j=right; Elem Type temp=R[i]; while(i while((R[j]>temp)&&(j>i)) j=j-1; if(j>i) { R[i]=R[j]; i=i+1; } while((R[i]<=temp)&&(j>i)) i=i+1; if(i R[j]=R[i]; j=j-1; } } R[i]=temp; if(left 写出二个串的比较算法 int strcmp(seqstring S seqstring T) { int j=1,k=1; while(j<=S.curlen)&&(k<=T.curlen) if(S.ch[j]!=T.ch[k]) return S.ch[j]-T.ch[k]; else{ j++;k++;} if(S.curlen==T.curlen) return 0; else if (S.curlen>T.curlen) return S.ch[j]; else return 0-T.ch[k]; } 写出顺序查找算法。并说明顺序查找的平均查找长度。 const int n=maxn struct node { ... elemtype key; }; int seqsearch(node R[n+1],elemtype k) { R[0].key=k;int i=n; wile(R[i].key!=k) i- -; return i; } 二叉树前序: void bitree::preorder(bitree *root) { bitree *P; p=root; if(p!=NULL) { cout< 中根遍历： void bitree::inorder(biteee *root) { bitree *p; p=root; if(p!=NULL) { inorder(p->lchild); cout< 后根遍历： void bitree::postorder( bitree *root) { bitree *p; p=root; if(p!=NULL) { postorder(p->lchild); posterder(p->rchild); cout<