第一章 概论 第一章 概论 测验

1、 问题:算法分析的两个主要方面是( )。
选项:
A:空间复杂度和时间复杂度
B:正确性和简单性
C:可读性和文档性
D:数据复杂性和程序复杂性
答案: 【空间复杂度和时间复杂度

2、 问题:具有线性结构的数据结构是( )。
选项:
A:图
B:树
C:广义表(线性表的推广)
D:栈
答案: 【

3、 问题:下面程序段的时间复杂度是( )。 for(i=0;iO(m*n)】

4、 问题:抽象数据类型的三个组成部分分别为( )。
选项:
A:数据对象、数据关系和基本操作
B:数据元素、逻辑结构和存储结构
C:数据项、数据元素和数据类型
D:数据元素、数据结构和数据类型
答案: 【数据对象、数据关系和基本操作

5、 问题:某算法的语句执行频度为(3n+nlog2n+n^2+8),其时间复杂度表示( )。
选项:
A:O(n)
B:O(nlog2n) (注:2是底)
C:O(n^2)(注:n的平方)
D:O(log2n)(注:2是底)
答案: 【O(n^2)(注:n的平方)

第二章 线性表 第二章 线性表 测验

1、 问题:在线性表的下列存储结构中,读取元素花费的时间最少的是( )。
选项:
A:单链表
B:双链表
C:循环链表
D:顺序表
答案: 【顺序表

2、 问题:在一个单链表中,若删除p所指向结点的后续结点,则执行( )。
选项:
A:p->next = p->next->next;
B:p = p->next; p->next = p->next->next;
C:p = p->next;
D:p = p->next->next;
答案: 【p->next = p->next->next;

3、 问题:已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为( )。
选项:
A:q->next=s->next;s->next=p;
B:s->next=p;q->next=s->next;
C:p->next=s->next;s->next=q;
D:s->next=q;p->next=s->next;
答案: 【q->next=s->next;s->next=p;

4、 问题:在一个单链表中,已知q所指结点是p所指结点的前驱结点,若在q和p之间插入一个结点s,则执行( )。
选项:
A:s->next=p->next; p->next=s;
B:p->next=s->next;s->next=p;
C:q->next=s;s->next=p;
D:p->next=s;s->next=q;
答案: 【q->next=s;s->next=p;

5、 问题:线性表L=(a1,a2,……,an),下列说法正确的是( )。
选项:
A:每个元素都有一个直接前驱和一个直接后继
B:线性表中至少要有一个元素
C:表中诸元素的排列顺序必须是由小到大或由大到小
D:除第一个和最后一个元素外,其余每个元素都由一个且仅有一个直接前驱和直接后继
答案: 【除第一个和最后一个元素外,其余每个元素都由一个且仅有一个直接前驱和直接后继

6、 问题:1、函数GetElem实现返回单链表的第i个元素,请在空格处将算法补充完整。int GetElem(LinkList L,int i,Elemtype e){ LinkList p;int j; p=L->next; j=1; while(p&&ji) return ERROR; e = p-data; return OK;}
答案: 【p=p->next

7、 问题:函数实现单链表的插入算法,请在空格处将算法补充完整。int ListInsert(LinkList L,int i,ElemType e){ LNode p,s;int j; p=L;j=0; while((p!=NULL)&&(jnext;j++; } if(p==NULL||j>i-1) return ERROR; s=(LNode *)malloc(sizeof(LNode)); s->data=e; ; p-next=s; return OK;}
答案: 【s-next=p-next

8、 问题:函数ListDelete_sq实现顺序表删除算法,请在空格处将算法补充完整。int ListDelete_sq(Sqlist *L, int i){ int k; if(i<1||i>L->length) return ERROR; for(k=i-1;klength-1;k++) L->slist[k] = ; –L->Length ; return OK;}
答案: 【L->slist[k+1]

9、 问题:函数实现单链表的删除算法,请在空格处将算法补充完整。int ListDelete(LinkList L,int i,ElemType s){ LNode p,q; int j; p=L;j=0; while((p-next!=null)&&(jnext; j++; } if(p->next==NULL||j>i-1) return ERROR; q=p->next; ‍; s=q->data; free(q); return OK;}
答案: 【p-next=q-next

10、 问题:下面程序段的功能是利用从尾部插入的方法建立单链表的算法,请在下划线处填上正确的内容。typedef struct node{ int data; struct node next;}lklist; void lklistcreate(lklist &head){ for (i=1; i<=n; i++) { p=(lklist )malloc(sizeof(lklist)); scanf(“%d”, &(p->data)); p->next=NULL; if(i==1) head=q=p; else { q->next=p; ; } } }/lklistcreate/
答案: 【q=p

第三章 栈与队列 第三章 栈和队列 测验

1、 问题:设计一个判别表达式中括号是否配对的算法,采用( )数据结构最佳。
选项:
A:顺序表
B:链表
C:队列
D:栈
答案: 【

2、 问题:判断一个循环队列Q(最多n个元素)为满的条件是( )。
选项:
A:Q->rear==Q->front
B:Q->rear==Q->front+1
C:Q->front==(Q->rear+1)%n
D:Q->front==(Q->rear-1)%n
答案: 【Q->front==(Q->rear+1)%n

3、 问题:一个顺序栈S,其栈顶指针为top,则将元素e入栈的操作是( )。
选项:
A: S->top=e;S->top++;
B:S->top++;
S->top=e;
C:S->top=e
D:S->top=e;
答案: 【
S->top=e;S->top++; 】

4、 问题:在一个链队列中,front和rear分别为头指针和尾指针,则插入一个结点s的操作为( )。
选项:
A:front=front->next;
B:s->next=rear;rear=s;
C:rear->next=s;rear=s;
D:s->next=front;front=s;
答案: 【rear->next=s;rear=s;

5、 问题:在解决计算机主机和打印机之间速度不匹配问题时,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个( )结构。
选项:
A:堆栈
B:队列
C:数组
D:线性表
答案: 【队列

6、 问题:栈和队列都是( )。
选项:
A:链式存储的线性结构
B:链式存储的非线性结构
C:限制存取点的线性结构
D:限制存取点的非线性结构
答案: 【限制存取点的线性结构

7、 问题:已知栈的4个基本操作函数: (a) int InitStack(SqStack S); //构造空栈 (b) int StackEmpty(SqStack S); //判断栈空 (c) int Push(SqStack S,ElemType e); //入栈 (d) int Pop(SqStack S,ElemType e); //出栈函数conversion实现十进制数转换为八进制数,请将函数补充完整。void conversion( ){ InitStack(S); scanf(“%d”, &N); //N为输入的十进制数 while(N) { ; N=N/8; } while(!StackEmpty(S)) { Pop(S, &e); //获取栈S中八进制的数字,赋值给e printf(“%d”, e); }}/conversion*/
答案: 【Push(S,N%8)

8、 问题:一个循环队列Q的存储空间大小为M,其队头和队尾指针分别为front和rear,则循环队列中元素的个数为( )。
答案: 【(rear-front+M)%M

9、 问题:3、阅读算法f1, 设队列Q=(1,3,5,2,4,6)。写出执行算法f1后的队列Q;注, 答案如:1,2,3,4,5,6void f1(Queue *Q){ DataType e; if (!QueueEmpty(Q)) { e=DeQueue(Q); f1(Q); EnQueue(Q,e); }}
答案: 【6,4,2,5,3,1

10、 问题:正常情况下,删除非空的顺序存储结构的堆栈的栈顶元素,栈顶指针top的变化是top= 。
答案: 【top-1

第五章 二叉树 第五章 二叉树前半部分(5.1~5.4)测验

1、 问题:下列关于二叉树性质的说法正确的有:(多选)Which sentences of the followings are right about a binary tree’s characterization:(There are more than one correct answers)
选项:
A:非空满二叉树的结点个数一定为奇数个。 The amount of nodes of a full binary tree with at least one node must be odd.
B:非完全二叉树也可以用像完全二叉树那样使用顺序存储结构进行存储。Sequential storing structure can also be used to store an incomplete binary tree just like to store a complete binary tree.
C:当一棵完全二叉树是满二叉树时,叶子结点不一定集中在最下面一层。If a complete binary tree is a full binary tree, it will be possible that leaf nodes is no t on the nethermost layer.
D:完全二叉树最多只有最下面的一层结点度数可以小于2。For a complete binary tree, only the degrees of nodes on the nethermost layer could be less than 2.
E:一棵非空二叉树的为空的外部结点数目等于其结点数加1。The amount of external null nodes in a binary tree with at least one node equals to its amount of nodes plus 1.
F:满二叉树的所有结点的度均为2。All degrees of nodes in a full binary tree are 2.
答案: 【非空满二叉树的结点个数一定为奇数个。 The amount of nodes of a full binary tree with at least one node must be odd.;
当一棵完全二叉树是满二叉树时,叶子结点不一定集中在最下面一层。If a complete binary tree is a full binary tree, it will be possible that leaf nodes is no t on the nethermost layer.;
一棵非空二叉树的为空的外部结点数目等于其结点数加1。The amount of external null nodes in a binary tree with at least one node equals to its amount of nodes plus 1.

2、 问题:下列关于二叉树遍历的说法正确的有:Which sentences of the followings are right about traversal of a binary tree:
选项:
A:前序和中序遍历的顺序恰好一样的二叉树,只能是空二叉树或者独根二叉树这两种情况。Only the sequences of preorder and infix order of the binary tree with no nodes or only one node are the same.
B:所有结点左子树为空的二叉树的前序和中序遍历顺序恰好一样。The sequences of preorder and infix order of a binary tree with all nodes without left child tree are the same.
C:所有结点右子树为空的二叉树的前序和中序遍历顺序恰好一样。The sequences of preorder and infix order of a binary tree with all nodes without right child tree are the same.
D:只有空二叉树和一个根结点的二叉树这两种二叉树的前序和后序遍历的顺序恰好一样。Only the sequences of preorder and post order of the binary tree with no nodes or only one node are the same.
E:所有结点左子树为空的二叉树的前序和后序遍历顺序恰好一样。The sequences of preorder and post order of a binary tree with all nodes without left child tree are the same.
F:所有结点右子树为空的二叉树的前序和后序遍历顺序恰好一样。The sequences of preorder and post order of a binary tree with all nodes without left child tree are the same.
G:只有空二叉树和一个根结点的二叉树这两种二叉树的中序和后序遍历的顺序恰好一样。Only the sequences of infix order and post order of the binary tree with no nodes or only one node are the same.
H:所有结点左子树为空的二叉树的中序和后序遍历顺序恰好一样。The sequences of infix order and post order of a binary tree with all nodes without left child tree are the same.
I:所有结点右子树为空的二叉树的中序和后序遍历顺序恰好一样。The sequences of infix order and post order of a binary tree with all nodes without right child tree are the same.
J: 存在一棵非空二叉树,它的前序、中序和后序遍历都是一样的。There exists a binary tree with at least one node, whose preorder, infix order and post order are all the same.
答案: 【所有结点左子树为空的二叉树的前序和中序遍历顺序恰好一样。The sequences of preorder and infix order of a binary tree with all nodes without left child tree are the same.;
只有空二叉树和一个根结点的二叉树这两种二叉树的前序和后序遍历的顺序恰好一样。Only the sequences of preorder and post order of the binary tree with no nodes or only one node are the same.;
所有结点右子树为空的二叉树的中序和后序遍历顺序恰好一样。The sequences of infix order and post order of a binary tree with all nodes without right child tree are the same.;
存在一棵非空二叉树,它的前序、中序和后序遍历都是一样的。There exists a binary tree with at least one node, whose preorder, infix order and post order are all the same.

3、 问题:一棵有510个结点的完全二叉树的高度为多少?(独根树高度为1)What is the height of a complete binary tree with 510 nodes? (the height of a tree with only a root is 1)
答案: 【9

4、 问题:一棵有512个结点的完全二叉树的高度为多少?(独根树高度为1)What is the height of a complete binary tree with 512 nodes? (the height of a tree with only a root is 1)
答案: 【10

5、 问题:在一棵非空二叉树中,若度为0的结点的个数n,度为2的结点个数为m,则有n=_ (系统根据字符串匹配来判定答案,所以您的答案中请不要包含空格) For a binary tree with at least one node, if there are n nodes with degree 0 and m nodes with degree 2, then n = _(This problem is judged by string matching, Please make sure your answer don’t contain any blanks.)
答案: 【m+1
分析:【设这棵二叉树总共有k个结点。因为二叉树的边数等于结点数减去1,并且二叉树的度数只有3种,分别是0,1,2。由此可得,2m+(k-n-m)=k-1。化简得,n=m+1.
Let the binary tree have n nodes. Since the edges of a binary tree are 1 less than nodes, and there are only 3 kinds of degree, 0, 1, 2. So, 2m+(k-n-m)=k-1. After simplification, n=m+1】

6、 问题:已知一棵树的前序遍历为ABDEGCF,中序遍历为DBGEACF,求这棵树的后序遍历。(字母和字母之间不要有空格)The preorder sequence of a tree is ABDEGCF, and its infix order sequence is DBGEACF, please write down its post order sequence. (There is no blank space between letters)
答案: 【DGEBFCA

7、 问题:已知一棵树的中序遍历为DBGEACF,后序遍历为DGEBFCA,求这棵树的前序遍历。(字母和字母之间不要有空格)The infix order sequence of a tree is DBGEACF, and its post order sequence is DGEBFCA, please write down its preorder sequence. (There is no blank space between letters)
答案: 【ABDEGCF

8、 问题:请写出下面这棵二叉树的前序遍历(字母和字母之间不要有空格)
Please write down the preorder sequence of the following binary tree. (There is no blank space between letters)
答案: 【BEXLMKCPDHQA
分析:【根-左-右 root-left-right】

9、 问题:请写出下面这棵二叉树的中序遍历(字母和字母之间不要有空格)
Please write down the infix order sequence of the following binary tree. (There is no blank space between letters)
答案: 【LXMECKPBQHDA
分析:【左-根-右 left-root-right】

10、 问题:请写出下面这棵二叉树的后序遍历(字母和字母之间不要有空格)
Please write down the post order sequence of the following binary tree. (There is no blank space between letters)
答案: 【LMXCPKEQHADB
分析:【左-右-根 left-right-root】

第五章 二叉树 第五章 二叉树后半部分(5.5~5.7)测验

1、 问题:下列关于二叉搜索树的说法正确的有Which sentences of the followings are right about binary search tree:
选项:
A:二叉搜索树按照中序遍历将各结点打印出将各结点打印出来,将得到按照由小到大的排列。If we print a binary search tree’s nodes according its infix order, the sequence will be from small to large.
B:如果结点χ的左子树有右子树,则存在某个结点的值介于结点χ的值和χ左儿子的值之间,并且这个结点在$$x$$的左子树之中。If the left child tree of a node x has a right child tree, then there exists some node whose value is between the value of node x and the value of its left child node, and this node is on the left child tree of node x.
C:当根结点没有左儿子时,根结点一定是值最小的结点。If the root node doesn’t have left child, it must be the node with the smallest value.
D: 二叉搜索树一定是满二叉树。A binary search tree must be a full binary tree.
E:二叉搜索树一定是完全二叉树。A binary search tree must be a complete binary tree.
F: 从根结点一直沿右儿子向下找不一定能找到树中值最大的结点。Along the right child of nodes all the time from the root node, it is possible that we couldn’t find out the node with the largest value.
答案: 【二叉搜索树按照中序遍历将各结点打印出将各结点打印出来,将得到按照由小到大的排列。If we print a binary search tree’s nodes according its infix order, the sequence will be from small to large.;
如果结点χ的左子树有右子树,则存在某个结点的值介于结点χ的值和χ左儿子的值之间,并且这个结点在$$x$$的左子树之中。If the left child tree of a node x has a right child tree, then there exists some node whose value is between the value of node x and the value of its left child node, and this node is on the left child tree of node x.;
当根结点没有左儿子时,根结点一定是值最小的结点。If the root node doesn’t have left child, it must be the node with the smallest value.

2、 问题:下列关于堆的说法正确的有: Which sentences of the followings are right:
选项:
A:堆一定是满二叉树。A heap must be a full binary tree.
B:最小堆中,最下面一层最靠右的结点一定是权值最大的结点。In a minimum heap, the rightest node on the nethermost layer must be the node with the largest value.
C:堆是实现优先队列的惟一方法。A heap is the only method to implement a priority queue.
D:堆一定是完全二叉树。A heap must be a complete binary tree.
E:最小堆中,某个结点左子树中最大的结点可能比右子树中最小的结点小。In a minimum heap, the largest value on some node’s left child tree could be possibly smaller than the smallest value of its right child tree.
F:使用筛选法建堆要比将元素一个一个插入堆来建堆效率高。Screening method has a higher efficiency than inserting elements one by one while constructing a heap.
答案: 【堆一定是完全二叉树。A heap must be a complete binary tree.;
最小堆中,某个结点左子树中最大的结点可能比右子树中最小的结点小。In a minimum heap, the largest value on some node’s left child tree could be possibly smaller than the smallest value of its right child tree.;
使用筛选法建堆要比将元素一个一个插入堆来建堆效率高。Screening method has a higher efficiency than inserting elements one by one while constructing a heap.

3、 问题:下列关于Huffman树和Huffman编码的说法正确的有:Which sentences of the followings are right about Huffman tree and Huffman code:
选项:
A:Huffman树一定是满二叉树。A Huffman tree must be a full binary tree.
B:Huffman编码是一种前缀编码。Huffman code is a kind of prefix code.
C:Huffman树一定是完全二叉树。A Huffman tree must be a complete binary tree.
D:Huffman编码中所有编码都是等长的。All codes in a Huffman code have the same length.
E: 对于同样的一组权值两两不同的内容可以得到不同的Huffman编码方案。Different content with the same group of weights can get different Huffman codes.
F:使用频率越高的字母,Huffman编码越长。The higher a letter’s frequency is, the longer its Huffman code is.
答案: 【Huffman树一定是满二叉树。A Huffman tree must be a full binary tree.;
Huffman编码是一种前缀编码。Huffman code is a kind of prefix code.;
对于同样的一组权值两两不同的内容可以得到不同的Huffman编码方案。Different content with the same group of weights can get different Huffman codes.

4、 问题:一组包含不同权的字母已经对应好Huffman编码,如果某一个字母对应编码001,下面说法正确的有A group of letters with different weights has corresponded with Huffman codes, if a letter’s corresponding code is 001, which sentences of the followings are right:
选项:
A: 以001开头的编码不可能对应其他字母。A code beginning with 001 couldn’t correspond with other letters.
B:以000开头的编码不可能对应任何字母。Codes beginning with 000 couldn’t correspond with any letter.
C: 以01开头和1开头的编码肯定对应某个字母。Codes beginning with 01 or 1 must correspongding with some letters.
D:建好的Huffman树至少包含4个叶结点。The Huffman tree contains at least 4 leaf nodes.
E:编码0和00可能对应于其他字母。Code 0 and 00 could corresponding with other letters.
答案: 【 以001开头的编码不可能对应其他字母。A code beginning with 001 couldn’t correspond with other letters.;
以01开头和1开头的编码肯定对应某个字母。Codes beginning with 01 or 1 must correspongding with some letters.;
建好的Huffman树至少包含4个叶结点。The Huffman tree contains at least 4 leaf nodes.

5、 问题:如果按关键码值递增的顺序依次将n个关键码值插入到二叉搜索树中,如果对这样的二叉搜索树进行检索时,每次检索的字符都等概率的从这n个关键码值中选取,平均比较次数为多少?If we insert n key values to a binary search tree successively from small to large, when we search this binary search tree, each time the search character is selected from these n key values with the same possibility, then how many times will the comparison be on average?
答案: 【(以下答案任选其一都对)(n+1)/2;
(1+n)/2

6、 问题:从空二叉树开始,严格按照二叉搜索树的插入算法(不进行旋转平衡),逐个插入关键码{18,73,10,5,68,99,27,41,51,32,25}构造出一棵二叉搜索树,对该二叉搜索树按照前序遍历得到的序列为?(答案中每两个元素之间用一个空格隔开)From a null binary tree, insert key values {18, 73, 10, 5, 68, 99, 27, 41, 51, 32, 25} successively according to the insertion algorithm of a binary search tree strictly (no rotation and balance) to construct a binary search tree. Please write down the sequence of preorder of this binary search tree. (There is one blank space between two elements)
答案: 【18 10 5 73 68 27 25 41 32 51 99

7、 问题:从空二叉树开始,严格按照二叉搜索树的插入算法(不进行旋转平衡),逐个插入关键码{18,73,10,5,68,99,27,41,51,32,25}构造出一棵二叉搜索树,对该二叉搜索树按照后序遍历得到的序列为?(答案中每两个元素之间用一个空格隔开)From a null binary tree, insert key values {18, 73, 10, 5, 68, 99, 27, 41, 51, 32, 25} successively according to the insertion algorithm of a binary search tree strictly (no rotation and balance) to construct a binary search tree. Please write down the sequence of post order of this binary search tree. (There is one blank space between two elements)
答案: 【5 10 25 32 51 41 27 68 99 73 18

8、 问题:从空二叉树开始,严格按照二叉搜索树的插入算法(不进行旋转平衡),逐个插入关键码构造出一棵二叉树,以怎样的顺序插入关键码集合{14,32,47,6,9,12,78,63,29,81}可以使得树的深度最小?请依次写出插入到树中的元素,每两个元素之间用一个空格隔开。如果有多组满足要求的方案,请使得你的答案中先插入的元素尽可能的小。From a null binary tree, insert key values successively according to the insertion algorithm of a binary search tree strictly (no rotation and balance) to construct a binary search tree. What is the insertion sequence that could make the tree have a smallest depth with a key value set {14,32,47,6,9,12,78,63,29,81}? Please write down the elements successively, and there is one blank space between two elements. If there are more than one answer that meet the condition, please make the element which needs to be inserted first as small as possible in your answer.
答案: 【12 6 9 47 29 14 32 78 63 81
分析:【通过 log_2{10}=4可以得到树的最小层数。然后因为需要保证先插入的元素尽可能的小,所以可以使得右子树尽可能的满。构造出这样一棵二叉搜索树后,按照前序遍历可以得出答案。 答案为12 6 9 47 29 14 32 78 63 81】

9、 问题:对于关键码序列{38,64,52,15,73,40,48,55,26,12},用筛选法建最小值堆,若一旦发现逆序对就进行交换,共需要交换元素多少次?For the key value sequence {38,64,52,15,73,40,48,55,26,12}, use the screening method to constuct a minimum heap, if we exchange them when we find reversed order, then how many times should we exchange them?
答案: 【6
分析:【73和12进行交换,52和40进行交换,64和12进行交换,38和12进行交换,38和15进行交换,38和26进行交换,一共6次。
Exchang

剩余60%内容付费后可查看
   

发表评论

电子邮件地址不会被公开。 必填项已用*标注