发布时间 : 星期日 文章判断题更新完毕开始阅读
依次前移_____个元素。
A、n-i B、n-i+1 C、n-i-1 D、i
（ ）82.在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为_____。
A、n B、n/2 C、(n+1)/2 D、(n-1)/2
（ ）83．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行_____ 。
A、HL = p; p->next = HL; C、p->next = HL; p = HL;
B、p->next = HL; HL = p; D、p->next = HL->next; HL->next = p;
（ ）84．在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行_____。
A、q->next = p->next ; p->next = q; C、q->next = p->next; p->next = q; B、p->next = q->next; q = p; D、p->next = q->next ; q->next = p; （ ）85．在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行_____。
A、p = q->next ; p->next = q->next; C、p = q->next ; q->next = p->next; B、p = q->next ; q->next = p; D、q->next = q->next->next; q->next = q; （ ）86. 在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的________。
A、 行号 B、 列号 C、 元素值 D、 地址
（ ）87. 设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为_______。
A、 O(1) B、 O(n) C、 O(n2) D、 O(log2n)
（ ）88．栈的插入与删除操作在_____进行。
A、栈顶 B、栈底 C、任意位置 D、指定位置
（ ）89．当利用大小为N的一维数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行_____语句修改top指针。
A、top++ B、top-- C、top=0 D、top
（ ）90．若让元素1，2，3依次进栈，则出栈次序不可能出现_____种情况。
A、3，2，1 B、2，1，3
17
C、3，1，2 D、1，3，2
（ ）91．在一个循环顺序队列中，队首指针指向队首元素的_____位置。
A、前一个 B、后一个 C、当前 D、后面
（ ）92．当利用大小为N的一维数组顺序存储一个循环队列时，该队列的最大长度为_____。
A、N-2 B、N-1 C、N D、N+1
（ ）93．从一个循环顺序队列删除元素时，首先需要_____。
A、前移一位队首指针 B、后移一位队首指针
C、取出队首指针所指位置上的元素 D、取出队尾指针所指位置上的元素
（ ）94．假定一个循环顺序队列的队首和队尾指针分别为f和r，则判断队空的条件是_____。
A、f+1==r B、r+1==f C、f==0 D、f==r
（ ）95．假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件是_____。
A、front==rear B、front!=NULL C、rear!=NULL D、front==NULL
四、应用题：
1、栈和队列都是特殊线性表，其特殊性是什么？
2、设有一顺序队列sq，容量为5，初始状态sq.front=sq.rear=0，划出作完下列操作的队列及其头尾指针变化状态，若不能入队，简述理由后停止。 1）d,e,b 入队。 2）d,e 出队。 3） i,j 入队。 4）b 出队。 5）n,o,p 入队。
3、设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为多少？
4、将两个栈存入数组V[1..m]中应如何安排最好?这时栈空、栈满的条件是什么? 5、已知稀疏矩阵如下：
请写出该稀疏矩阵三元组表示。
6、广义表A=（a,b,(c,d),(e,(f,g))）,求其长度，及深度。
18
7、请画出下面广义表相应的加入表头结点的单链表表示，
D(A(x,y,L(a,b))，B(z,A(x,y,L(a,b))))。
8、一棵具有n个结点的理想平衡二叉树（即除离根最远的最底层外其他各层都是满的，最底层有若干结点）有多少层？若设根结点在第0层，则树的高度h如何用n来表示（注意n可能为0）？
9、设二叉树后根遍历为BAC，画出所有可能的二叉树。
10、假设一棵二叉树的层序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,请画出该树。
11、有一个完全二叉树按层次顺序存放在一维数组中，如下所示：
请指出结点P的父结点，左子女，右子女。 12、给出下列二叉树的先序序列。
13、已知某非空二叉树采用顺序存储结构，树中结点的数据信息依次存放在一个一维数组中，
即
ABC□DFE□□G□□H□□，该二叉树的中序遍历序列为：
14、设一棵二叉树的前序序列为1,2,3,4,5,6,7,8,9,其中序序列为2,3,1,5,4,7,8,6,9,试画出该二叉树。 15、已知一组元素为（46，25，78，62，12，37，70，29），试画出按元素排列次序插入生成的
一棵二叉树。
16、由于元素插入的次序不同，所构成的二叉排序树也有不同的状态，请画出一棵含有1，2，
3，4，5，6六个结点且以1为根，深度为4的二叉排序树。 17、什么是线索二叉树？为什么要线索化？
18、有n个顶点的有向连通图最多有多少条边?最少有多少条边？ 19、下图中给出由7个顶点组成的无向图。从顶点1出发，
对它进行深度优先遍历得到的顶点序列是： 进行广度优先遍历得到的顶点序列是：
20、什么是连通图的生成树？
19
21、什么是哈夫曼（Huffman）树？
22、已知结点a,b,c,d及其权值写出哈夫曼树的构造过程。 a b c d 7 5 2 4 23、已知图G={V , E} V={ a, b, c, d, e }
E={(a, b),(b, d),(c, d),(d, e),(e, a),(a, c)} 画出图G，画出图G的邻接表。 24、考虑下图：
1）从顶点A出发，求它的深度优先生成树。 2）从顶点E出发，求它的广度优先生成树。
3）根据普里姆（Prim）算法，求它的最小生成树。
25、设有关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序
进行排序。
若采用初始步长为4的Shell排序法，则一趟扫描的结果是：
若采用以第一个元素为分界元素的快速排序法，则一趟扫描的结果是：
26、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为
基准而得到的第一次划分结果为：
27、用二分法对一个长度为10的有序表进行查找，填写查找每个元素需要的比较次数。 下标： 0 1 2 3 4 5 6 7 8 9 比较次数：
28、若对序列(49,38,27,13,97,76,50,65)采用泡排序法(按照值的大小从小到大)进行排序，请分别在下
表中写出每一趟排序的结果。
原始序列 49 38 27 13 97 76 50 65 第1趟的结果 第2趟的结果 第3趟的结果 第4趟的结果
29、给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序
时的变化过程：
1）归并排序 每归并一次书写一个次序。
2）快速排序 每划分一次书写一个次序。
20