1. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，
当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1
大小为6的数组：下标从0-5;从前面出队，从后面入队 front(前面)=3 rear(后面)=0
当出队列中删除一个元素，也就是出队，即front+1:=4 再插入两个元素，即rear+2= 2
【注】
循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是\"空\"还是\"满\"。
2. 循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队
列中的元素数是( )。 A. (rear-front+m)%m C. rear-front-1 3. for（i=0；i 上面算法的时间复杂度为( ) A.O(m2) C.O(m×n) B.O(n2) D.O(m+n） B. rear-front+1 D. rear-front 4. 设h是指向非空带表头结点的循环链表的头指针，p是辅助指针。执行程序段 p=h; while (p->next->next!=h) p=p->next; p->next=h; 后（其中，p->next为p指向结点的指针域），则( ) A. p->next指针指向链尾结点 C. 删除链尾前面的结点 B. h指向链尾结点 D. 删除链尾结点 5. 假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（ ） A.head= =NULL C.head!=NULL B.head–>next= =NULL D.head–>next= =head 6. 设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个 元素的存储地址为( ) A.236 B.239 C.242 D.245 7. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A．9 B．11 C．15 D．不确定 8. n个结点的线索二叉树上含有的线索数为（ ） A．2n B．n－l C．n＋l D．n 9. 设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是( ) A.DCBA C.DBAC B.CDAB D.DCAB 10. 归并排序中，归并的趟数是( )。 A．O（n） B．O(logn) C．O(nlogn) D．O(n*n) 11. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素， 其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。 A. 13 C. 18 12. 栈和队列的共同点是（ ）。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点 13. 某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是( ) A.高度等于其结点数 C.任一结点无右孩子 B.任一结点无左孩子 D.空或只有一个结点 B. 33 D.40 14. 排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是( ) ．．． A.选择排序 C.冒泡排序 15. 若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不超过( ) nA. 2 B. n B.插入排序 D.快速排序 n1C. 2 D. n+1 16. 在排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进 行比较，将其放入已排序序列的正确位置上的方法，称为( ) A.希尔排序 C.冒泡排序 B.插入排序 D.快速排序得分 17. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) A．（100,80,90,60,120,110,130） B. (100,120,110,130,80, 60, 90） C.（100,60,80,90,120,110,130） D. (100,80, 60, 90, 120,130,110) 18. 下面关于二分查找的叙述正确的是 ( ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储 19. 采用简单选择排序，比较次数与移动次数分别为( )。 A. O（n）,O(logn) C. 0(n*n),0(n) B. O(logn),0(n*n) D. 0(nlogn),0(n) 20. 下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。 A． 冒泡 B. 希尔 C. 快速 D. 堆 21. 二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二 叉树根的右子树的根是：( ) A、 E B、 F C、 G D、 H 22．在数据结构中，从逻辑上可以把数据结构分为( )。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构” 23．已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是( )。 A．acbed B．decab C．deabc D．cedba 24．非空的循环单链表L的尾结点p满足( )。 A．p->next＝NULL B． p->next=L C．p＝NULL D．p＝L 25．如果以链表作为栈的存储结构，则出栈操作时( )。 A．必须判别栈是否满 B．判别栈元素的类型 C．必须判别栈是否空 D．对栈不做任何判别 26．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( )存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 27．有64个结点的完全二叉树的深度为( )（根的层次为1）。 A．8 B．7 C．6 D．5 28．下面的排序为哪种排序法( ) 数组：8，6，3，2，9 排序： 第1步 6，3，2，8，9 第2步 3，2，6，8，9 第3步 2，3，6，8，9 第4步 2，3，6，8，9 A．插入排序法 B．快速排序法 C．冒泡排序法 D．选择排序法 29．在对n（n>3）个元素进行选择排序的过程中，在第 3 趟需要从( )个元素中选择出最小值元素。 A．n-2 B．n-3 C．3 D．4 30．循环队列的入队操作应为( )。 A．rear=rear+1; data[rear]=x; B．data[rear]=x; rear=rear+1; C．data[rear]=x; rear=(rear+1)%size; D． rear=(rear+1)%size; data[rear]=x; 31. 以下说法错误的是( )。 A. 二叉树可以是空集 B. 二叉树的任一节点都有两棵子树 C. 二叉树与树具有相同的树形结构 D. 二叉树中任一节点的两棵子树有次序之分 32．折半查找法适用于存储结构为( )，且按关键字已排好序的线性表 A.顺序存储 B.链接存储 C.顺序存储或链接存储 D.索引存储 33．设有序表的关键字序列为{1,4,6,10,18,35,42,53,67,71,78,84,92,99}，当用折半查找法查找关键字 67 的节点时，经( )次比较后查找成功。 A. 2 B. 3 C. 4 D. 12 34．在表长为 n 的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为( )。 A. n B. 1 C. n+1 D. n-1 35．一棵完全二叉树上有 11 个结点,其中叶子结点的个数是( ). A.4 B. 5 C.6 D. 7 36．有 12 个记录的序列,采用冒泡排序最少的比较次数是( ). A.1 B.144 C.11 D.66 A．acbed B．decab C．deabc D．cedba 37．采用折半查找方法查找长度为n的线性表时，每个元素的平均查找长度为___ ___。 2 A、O(n) B、O(nlog2n) C、O(n) D、(O(log2n) 38．任何一个无向连通图的最小生成树____________。 A．只有一棵 B．有一棵或多棵 C．一定有多棵 D．可能不存在 39．下列排序算法中，时间复杂度为O（nlog2n）且占用额外空间最少的是________。 A．堆排序 B．冒泡排序 C．快速排序 D．SHELL排序 40.若线性表最常用的操作是存取第i个元素及其前趋的值，则采用_______存储方式节省 时问。 A．单链表 B．双链表 C．单循环链表 D．顺序表 二、填空题 1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 存储结构。 2、 带头结点的双循环链表L为空表的条件是： 。 3、假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素A9,7在B中的存储位置k=_________________。 4、假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是________。假设根结点的层数为１，具有ｎ个结点的完全二叉树的最大高度是________。 5、前序序列和中序序列不相同的二叉树的特征是________________。 ． 6、在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为___________________。 7、 假设一棵完全二叉树含1000个结点,则其中度为2的结点数为________。 8、 在对一组关键字为（54，38，96，23，15，72，60，45，83）的记录采用直接选择排序 法进行排序时，整个排序过程需进行________趟才能够完成。 9、 己知有一个三对角矩阵A【1..9,1..9】的每个元素占2个单元，现将其三条对角线上的 元素逐行存储在起始地址为1000的连续的内存单元中，则元素A[7,8]的地址为___________ 10、 设F、C是二叉树中的两个结点，若F是C的祖先结点，则在采用后根遍历方法遍 历该二叉树时，F和C的位置关系为：F必定在C的________。 11、 12、 13、 在一棵二叉排序树上按___________遍历得到的结点序列是一个有序序列。 链式存储结构的特点是借助___________来表示数据元素之间的逻辑关系。 设只含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为 ________________,最小结点数为________________。 三、应用题 1、写出下图中二叉树的先根、中根、后根遍历序列。 2、书上139页第17，18题 3、 已知电文中只出现A、B、C、D、E五种字符，出现概率依次为15％，22％，10％，18％， 35％，求各符号的哈夫曼编码。要求图示哈夫曼树建立过程。 4、 对如下带权无向图，用克鲁斯卡尔(Kruskal)算法或普里姆（prim）算法，生成一棵最 小生成树，并且用图示来表明树的形成过程。 8 ① ② 21 3 11 15 5 19 ③ 6 ⑥ ④ 9 ⑤ 8 5、设有序列（23，37，7，79，29，43，19，31，66，36，48），图示出初始建堆过程（建 大根堆）。以及第一次输出堆顶元素后经过筛选调整的堆的完全二叉树形态。 6、 根据下图所示的邻接链表，画出相应的图；并据该邻接表，给出从A开始进行深度优先、 广度优先搜索得到的遍历序列。 0 V1 1 3 5 2 ∧ 1 V2 0 2 3 4 ∧ 2 V3 0 1 3 V4 1 0 5 ∧ 4 V5 1 ∧ 5 V6 0 3 ∧ 7、对给定的数列R＝｛7，16，4，8，20，9，6，18，5｝构造一棵二叉排序树，并且分别给出中序遍历序列和后序遍历序列。 8、书上224页第21、22、23小题 四、算法设计题（本大题共2小题，每小题8分，共16分） 1、已知head是指一个带头结点的单链表的头指针，链表内结点递增有序。试编写一算法，将值为x的结点插入链表合适位置，使得链表仍然有序。 2、某带头结点的单链表的结点结构说明如下： typedef struct node1 { int data; struct node1 *next }node； 试设计一个算法int copy(node *head1, node *head2)，将以head1为头指针的单链表复制到一个不带头结点且以head2为头指针的单链表中。 3、设线性表中的数据元素递增有序，并以单链表作存储结构，试写一算法 void Linklist ：：Delete_Del_Between (&L,int min,int max)， 删除表中所有值大于min且小于max的元素。（10分） 4、设计算法判断一个算术表达式的圆括号是否正确配对。 5、设计算法判断一字符串是否为回文。（该字符串用线性表的顺序存储） 因篇幅问题不能全部显示，请点此查看更多更全内容