一、选择题（每小题 1分，共10分）
1、队列是插入和删除受限的线性表，其删除操作是在线性表的（1）进行。
A．表头 B．表尾 C．任意位置 D．指定位置
2、下述哪一条是顺序存储结构的优点（2）。
A．存储密度大 B．插入运算方便
C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示
3、设有一个栈，元素的进栈次序为A, B, C, D, E，下列哪个是不可能的出栈序列（3）。
A．A, B, C, D, E B．B, C, D, E, A
C．E, A, B, C, D D．E, D, C, B, A
4、若二叉树的根结点所在的层次为第1层，则该二叉树的第k层上至多有（4）个
2k B．2k C．2k-1 D．2k+1结点。A. 1
5、设单链表中指针p指向结点m，若要删除m的后继结点（假设该后继结点存在），则需修改指针的操作为（5）。
A．p->next=p->next->next; B．p=p->next;
C．p=p->next->next; D．p->next=p;
6、下面程序段的时间复杂度为（6）。
for(int i=0; i for(int j=0; j A．O(m2) B．O(n2) C．O(m+n) D． O(m*n) 7、非空的循环单链表head的尾结点指针p满足（7）。 A．p==NULL B．p== head C．p->next==head D．p->next==NULL 8、已知二维数组A[0..9,0..9]中，元素a[2][0]的地址为560，每个元素占4个字节，则元素a[1][0]的地址为（8）。 A. 518 B. 520 C. 522 D. 524 9、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（9）。 A．rear％n= = front B．（front+l）％n= = rear C．rear％n -1= = front D．(rear+l)％n= = front 10、假设在一棵二叉树中，度为2的结点数为15，度为1的结点数为10个，则该二叉树的分支总数为（10）个。 A. 41 B. 40 C. 30 D. 25 二、填空题（每空2分，共20分） 1. 一棵深度为k的完全二叉树（假定根结点所在的层次为第1层），则其结点总数的最 小值为（1），最大值为（2）。 2．对于一个具有n个结点的单链表（n≥1），在指针变量p指向的结点后插入一个新结点的时间复杂度为（3），在给定值为x的结点后插入一个新结点的时间复杂度为（4）。 3. 设有一空栈，现有输入序列A，B，C，D，E，经过push, push, pop, push, pop, push, push后，此时的输出序列为（5）。 4. 有一个100*90整型数据的稀疏矩阵，非0元素有10个，设每个整型数据占2字节， 则用三元组表示该矩阵时，所需的字节数是（6）。 5. 设栈S和队列Q初始为空。6个元素依a,b,c,d,e,f的顺序通过栈S，一个元素出 栈后立即进入队列 Q。若这6个元素出队的序列为d,c,b,f,e,a，则栈S 的最小容量需（7）。 6. 若对n阶对称矩阵A[0..n-1,0..n-1]以行序为主序方式将其下三角形的元素(包括 主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定a ij（i≤j）的位置k的关系为（8）。 7. 表达式a+((b*c-d)/e+f*g/h)+x/y对应的后缀表达式是（9）。 8. 若INDEX（S，T）表示求T在S中的位置的操作，则对于S="Beijing＆Nanjing"， T="jing"，INDEX（S，T）= （10）。 三、判断题（每小题2分，共10分，错误打×，正确打√） 1．二叉树结构中，任何一个结点都有一个且仅有一个直接前驱和直接后继。 ............ ( ) 2．在一棵二叉树中，假定每个结点只有左孩子，没有右孩子，对它分别进行中序遍历和后序遍历，则具有相同的结果。 ............. ( ) 3. 对线性链表来说，从任意结点开始均能扫描表中全部结 点。 ............. ( ) 4. 线性表的特点是每个元素都有一个前驱和一个后 继。 ............. ( ) 5. 栈和队列都是限制存取点的线性结 构。 ............. ( ) 四、简答题(本大题有5小题，共 40 分，每小题分值见各题标注) 1．（6分）已知一棵二叉树如下，请分别写出按前序、中序、后序遍历时得到的字符序列。 A B C D E F G H I 2．（6分）设x，n为整型变量，且n>0，下面程序片段中语句x /= 2执行次数的数量级是多少试进行分析。用“O”记号表示。 x = n*n; while (x>=1) x /= 2; 3．（8分）用栈实现将中缀表达式：8*(3+5)+5/3# 转换成后缀表达式，画出栈的变化过程图（符号“#”为表达式结束符）。 4．（10分）已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树，并写出对其先序遍历的序列。 5. （10分）线性表有两种常用存储结构：一是顺序表，二是线性链表。试问： （1）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动的改变。在此情况下，应选用哪种存储结构为什么 （2）若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，那么应采取哪种存储结构为什么 五、算法题(本大题有2小题，每题10分，共 20 分) 1. 以下算法利用栈的基本操作将一个十进制正整数转换成二进制正整数，填空完善之。 void conversion( ) { InitStack(S); scanf("%d",&x); while (x!=0) { push(S, （1） ); x=x/2; } while( !StackEmpty(S) ) { （2） ; printf("%d",x); } } 注：栈的基本操作如下： InitStack(s)：初始化一个栈； Push(s,x)：元素x进栈； Pop(s,x)：栈顶元素出栈； GetTop(s,x)：读出栈顶元素； StackEmpty(s)：判栈是否为空。 2. 编写二叉树（以二叉链表存储）先序遍历的递归算法。 答案 一、选择题(每小题 1分，共10分) 1—5. A A C A A 6.—10. D C B D B 二、填空题（每空2分，共20分） 1. 【1】2k-1 +1【2】2k-1 2. 【3】 O(1) 【4】O(n) 3. 【5】 B C 4. 【6】 60 5. 【7】 4 6. 【8】 7. 【9】 8. 【10】 4 三、判断题（每小题2分，共10分，错误打×，正确打√） 1．× 2．√ 3．× 4．× 5．√ 四、简答题(本大题有5小题，共 40 分，每小题分值见各题标注) 1．（6分） 解：前序遍历：A，B，D，E ，G，H ，J，C，F,I ................. (2分) 中序遍历：D，B，G，E，J，H，A，C，I，F ................. (2分) 后序遍历：D ，G ，J ，H ，E ，B ，I ，F ，C ，A ................. (2分) 2．（6分） 解： 根据题意，可知： 第1次循环时， 21*2 x n =； ................. (1分) 第2次循环时， 221 *2x n =； 第3次循环时， 23 1 *2x n =； 由此可作如下假设： 当x = 1或接近1时， 已经循环了k 次，则必有： 21*12 k x n ==， ................. (2分) =〉22k n = =〉22log n k = =〉22log n k =; 所以，x/=2执行次数的数量级是2(log )n O ................. (3分) 3．（8分） 解：后缀式为：835+*53/+，(3分) ； 栈的结构变化如下图所示（每图1分）： (1)(2) (3) (4)(5) 4．（10分）解：该二叉树如下： 先序遍历：A B C D E F G H ................. 5分 ................. 5分 5（10分）解： （1）在此情况下，应该选择线性链表的存储结构，应为各表的长度经常动态变化，意味着此表经常进行插入和删除的操作，而对于链表来说，插入一个元素或删除一个元素的算法复杂度为O(1)，比顺序存储结构的算法复杂度要小很多。................. 5分 （2）由于顺序存储结构对数据的存取方式是随机存取的，算法复杂度为O(1)；而链表对数据的存取方式是顺序存取的，算法复杂度为O(n)，所以应该选择顺序存储结构。........... 5分 五、算法题(本大题有2小题，每题10分，共 20 分) 1．解： （1） x%2 ................. 5分 (2) Pop( S, x ) ................. 5分 2．解：先序遍历递归算法如下： Status PreOrderTraverse( BiTree T , Status( *Visit )( TelemType e ) ){ ................. 2分 If( T ){ .................2分 If( Visit( T-> data ) ) ................. 2分 If( PreOrderTraverse( T->lchild, Visit ) ) ................. 2分 If( PreOrderTraverse( T->rchild, Visit ) ) ................. 2分 return OK; Return ERROR; } Else return OK; }
相关主题
文本预览