第1章概论1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①Ｃ、数据信息在计算机中的②A以及一组相关的运算等的课程。

①A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法2. 计算机算法指的是① C ，它必具备输入、输出和② B 等五个特性。

① A. 计算方法 B. 排序方法C. 解决问题的有限运算序列D. 调度方法② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性3.下面程序段的时间复杂度是Dfor(i=0;i<n;i++)for(j=1;j<m;j++)A[i][j]=0;A.O(n)B.O(m+n+1)C.O(m+n)D.O(m*n)4. 分析下面程序段，最大语句频度为n (n＋1)/2 ，该算法的时间复杂度是_ O (n2)_。

for (i=0;i<n;i++)for (j=0; j<i; j++)A[i][j]=0;5. 数据逻辑结构包括线性结构、树型结构和图型结构三种类型，树型结构和图型结构合称为非线性结构。

6. 线性结构中元素之间存在一对一关系，树型结构中元素之间存在一对多关系，图型结构中元素之间存在多对多关系。

第2章线性表1.在单链表中，已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？BA. 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；2.非空的不带头结点的循环单链表，首结点由first指向，尾结点由p指向，则满足：CA. p->next == NULL；B. p == NULL；C. p->next == first；D. p == first；3.在一个长度为n的顺序存储的线性表中，删除第i个元素（0≤i≤n-1）时，需要移动多少个元素？CA. n-iB. n-i+1C. n-i-1D. I4.在带头结点指针head的单链表中，链表为空的判断条件是？BA. head == NULLB. head->next == NULLC. head != NULLD. head->next == head；5.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是BA. p=p->next;B. p->next=p->next->next;C. p->next=p;D. p=p->next->next;6.在双链表中删除某个结点p，实现的语句是AA. p->prior->next=p->next; p->next->prior=p->prior;B. p->prior->next=p->next->prior; p->next->prior=p->prior;C. p->next=p->prior; p->prior=p->next;D. p->prior->next=p->next;7.在双链表中给定结点p之后插入一个新结点s，实现的语句是CA. s->next=p->next; s->prior=p; p->prior=s; p->next=s;B. p->next=s; s->next=p->next; s->prior=p; p->next->prior=s;C. s->next=p->next; s->prior=p; p->next->prior=s; p->next=s;D. s->next=p->next; s->prior=p; p->next=s; p->prior=s;8.在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。

9.在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有 1 个后续结点。

第3章栈和队列1.引起循环队列头位置发生变化的操作是？AA. 出对B. 入对C. 取对头元素D. 取对尾元素2.若进栈序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？CA. 1，3，2，4B. 2，3，4，1C. 4，3，1，2D. 3，4，2，13.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为BA．3，2，6，1，4，5 B．3，4，2，1，6，5C．1，2，5，3，4，6 D．5，6，4，2，3，14.一个队列的数据入队序列是1，2，3，4，则队列的出队时输出序列是？BA. 4，3，2，1B. 1，2，3，4C. 1，4，3，2D. 3，2，4，15.栈的两种常用存储结构分别为AA．顺序存储结构和链式存储结构 B．顺序存储结构和散列存储结构C．链式存储结构和索引存储结构 D．链式存储结构和散列存储结构6.已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为CA．5 B．6 C．16 D．177.已知循环队列的存储空间为数组data[25]，且当前队列的头指针和尾指针的值分别为10和5，则该队列的当前长度为？AA．20 B．25 C．10 D．158. 判定一个循环队列QU（最多元素为m0, m0= =Maxsize-1）为满队列的条件是A 。

A. ((rear- front)+ Maxsize)% Maxsize = =m0B. rear-front-1= =m0C. front= =rearD. front= = rear+19. 循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是A 。

A. (rear-front+m)%mB. rear-front+1C. rear-front-1D. rear-front10.栈和队列都是AA．限制存取位置的线性结构 B．顺序存储的线性结构C．链式存储的线性结构 D．限制存取位置的非线性结构11.队和栈的主要区别是DA.逻辑结构不同B.存储结构不同C.所包含的运算个数不同D.限定插入和删除的位置不同12.已知循环队列的存储空间为数组data[18]，且当前队列的头指针和尾指针的值分别为7和2，则该队列的当前长度为？AA．13 B．5 C．9 D．1813. 向量、栈和队列都是线性结构，可以在向量的_任何___位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入元素和队首删除元素。

第4章串第5章数组1. 二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是C 。

A. 80B. 100C.240D. 2702. 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为C 。

A. SA+141B. SA+144C. SA+222D. SA+2253. 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为B 。

A. SA+141B. SA+180C. SA+222D. SA+2254. 已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是__ LOC (A[0][0])+(n*i+j)*k _____。

5. 二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200，则A[6][12]的地址是__200+（6*20+12）= 326__。

6. 二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是_1000+((18-10)*6 +(9-5))*4 = 1208__。

第6章树1. 如图所示的4棵二叉树，C 不是完全二叉树。

(A) (B) (C) (D)2.任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序？BA.发生改变B.不发生改变C.不能确定D.以上都不对3.一棵含18个结点的二叉树的高度至少为CA. 3B. 4C. 5D. 64.按照二叉树的定义，具有3个结点的不同形状的二叉树有几种？AA. 5B. 4C. 3D. 65.对一个满二叉树，m个树叶，n个结点，深度为h，则? DA. n=h+mB. h+m=2nC. m=h-1D. n=2h-16. 一棵二叉树中双分支结点数为15，单分支结点数为30个，则叶子结点数为16 个。

7. 在一棵二叉树中，度为零的结点个数为n0，度为2的结点个数为n2，则有n= n2+1 。

8. 一棵二叉树的第i（i≥1）层最多有2i-1 个结点。

9. 已知完全二叉树T的第5层只有7个结点，则该树共有叶子结点数目为11 。

10. 深度为5的二叉树至多有31 个结点。

11. 某二叉树的前序遍历结果为stuwv，中序遍历为uwtvs，那么后序遍历为wuvts 。

12. 某二叉树的前序遍历为abdgcefh，中序遍历为dgbaechf，则后序遍历的为gdbehfca 。

13. 在树型结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个直接前驱结点，叶子结点没有后继结点，其余每个结点的直接后继结点可以任意多个。

14. 有一棵树如图所示，回答下面的问题：⑴这棵树的根结点是__ k1__；⑵这棵树的叶子结点是_ k2,k5,k7,k4___；⑶结点k3的度是_2___；⑷这棵树的度是_3___；⑸这棵树的深度是__4__；⑹结点k3的子女是__ k5,k6__；⑺结点k3的父结点是__ k1__；15.设字符a,b,c,d,e,f的使用权值分别是7, 9, 12, 22, 23, 27，画出Huffman树，并写出a,b,c,d,e,f的Huffman编码。