一、单选题（每题 2 分，共20分）
1. 1.对一个算法的评价，不包括如下（B ）方面的内容。
A．健壮性和可读性B．并行性C．正确性D．时空复杂度
2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。
A. p->next=HL->next; HL->next=p;
B. p->next=HL; HL=p;
C. p->next=HL; p=HL;
D. HL=p; p->next=HL;
3. 3.对线性表，在下列哪种情况下应当采用链表表示？( )
A.经常需要随机地存取元素
B.经常需要进行插入和删除操作
C.表中元素需要占据一片连续的存储空间
D.表中元素的个数不变
4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )
A. 2 3 1
B. 3 2 1
C. 3 1 2
D. 1 2 3
5. 5.AOV网是一种（）。
A．有向图B．无向图C．无向无环图D．有向无环图
6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。
A．低于链接法处理冲突 B. 高于链接法处理冲突
C．与链接法处理冲突相同D．高于二分查找
7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。
A．值B．函数C．指针D．引用
8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。
A．行号B．列号C．元素值D．非零元素个数
9.9.快速排序在最坏情况下的时间复杂度为（）。
A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)
10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A. O(n)
B. O(1)
C. O(log2n)
D. O(n2)
二、二、运算题（每题 6 分，共24分）
1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N）的联系
时，称这种结构为_____________________。
2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的____首______进行。
3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是
___top==0___(要超出才为满)_______________。
4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插
入元素的时间复杂度为____________。
5. 5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ，
则二维数组W的数据元素共占用＿_____＿个字节。W中第6 行的元素和第4 列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。
6. 6.广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。
7.7.二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结点的度的
总和是_____________。
8.8.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由算术表
达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。
9. 9. 对于一棵具有n 个结点的二叉树，用二叉链表存储时，其指针总数为_____________个，其中
_______________个用于指向孩子，_________________个指针是空闲的。
10. 10. 若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A 中，即编号为0的结点存储到A[0]中。其余类推，则A[ i ]元素的左孩子元素为________,右孩子元素为_______________，双亲元素为____________。
11. 11. 在线性表的散列存储中，处理冲突的常用方法有________________________和
_____________________________两种。
12. 12. 当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用_______________排序；
当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用________________________排序。 三、 三、 运算题（每题6分，共24分） 1. 1. 已知一个6?5稀疏矩阵如下所示，
试：
（1） （1）
写出它的三元组
线性表；
（2） （2） 给出三元组线性表的顺序存储表示。
2. 2. 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个数据而生
成的二叉搜索树。
3. 3. 对于图6所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序
号从小到大的次序链接的，试写出：
(1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树； (2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树； 4. 4. 已知一个图的顶点集V 和边集E 分别为：
V={1,2,3,4,5,6,7};
E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>}; 若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，按主教材中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列。
四、 四、 阅读算法（每题7分，共14分） 1. 1. int Prime(int n)
{
int i=1;
int x=(int) sqrt(n);
while (++i<=x)
????????????????????--00
7
00000520000000
100000010000
图6
if (n%i==0) break;
if (i>x) return 1;
else return 0;
}
(1)(1)指出该算法的功能；
(2)(2)该算法的时间复杂度是多少？
2. 2.写出下述算法的功能：
void AJ(adjlist GL, int i, int n)
{
Queue Q;
InitQueue(Q);
cout< visited[i]=true; QInsert(Q,i); while(!QueueEmpty(Q)) { int k=QDelete(Q); edgenode* p=GL[k]; while(p!=NULL) { int j=p->adjvex; if(!visited[j]) { cout< visited[j]=true; QInsert(Q,j); } p=p->next; } } } 五、五、算法填空（共8分） 如下为二分查找的非递归算法，试将其填写完整。 Int Binsch(ElemType A[ ],int n,KeyType K) { int low=0; int high=n-1; while (low<=high) { int mid=_______________________________； if (K==A[mid].key) return mid; //查找成功，返回元素的下标 else if (K<[mid].key) ______________________________________; //在左子表上继续查找 else __________________________________; //在右子表上继续查找 } return -1; //查找失败，返回-1 } 六、 六、 编写算法（共8分） HL 是单链表的头指针，试写出删除头结点的算法。 ElemType DeleFront(LNode * & HL) 参考答案 一、 一、 单选题（每题2分，共20分） 1.B 2.A 3.B 4.C 5.D 6.B 7.D 8.A 9.D 10.C 二、 二、 填空题（每空1分，共26分） 1. 1. 联系 图（或图结构） 2. 2. 尾 首 3. 3. top==0 4. 4. O （1） O （n ） 5. 5. 128 44 108 6. 6. 3 3 7. 7. 有序 n-1 8. 8. 有序序列 后缀表达式（或逆波兰式） 9. 9. 2n n-1 n+1 10. 10. 2i+1 2i+2 (i-1)/2 11. 11. 开放定址法 链接法 12. 12. 快速 归并 三、 三、 运算题（每题6分，共24分） 1. 1. （1） ((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)) (3分) （2） 三元组线性表的顺序存储表示如图7 示。 2. 2. 如图8所示。 3. 3. DFS ：①②③④⑤ BFS ：②③④⑤① 4. 4. 拓朴排序为： 4 3 6 5 7 2 1 四、 四、 阅读算法（每题7分，共14分） 1. 1. (1) 判断n 是否是素数（或质数） （2）O （n ） 2. 2. 功能为：从初始点v i 出发广度优先搜索由邻接表GL 所表示的图。 五、 五、 算法填空（8 分） (low+high)/2 high=mid-1 low=mid+1 六、 六、 编写算法（8分） ElemType DeleFront(LNode * & HL) { if (HL==NULL){ cerr<<"空表"< exit(1); 6 5 5 1 5 1 3 2 -1 4 5 -2 5 1 5 6 3 7 图7 图8 } LNode* p=HL; HL=HL->next; ElemType temp=p->data; delete p; return temp; } 一、一、单选题（每题 2 分，共20分） 1. 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2. 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3. 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个 元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5. 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6. 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找， 则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O（1） B. O（n） C. O（1og2n） D. O（n2） 9.9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作 为散列函数，则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 10.10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、二、填空题（每空1分，共26分） 1. 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2. 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3. 3. 假定一棵树的广义表表示为A （C ，D （E ，F ，G ），H （I ，J ）），则树中所含的结点数为__________ 个，树的深度为___________，树的度为_________。 4. 4. 后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X ）-2Y/3对应的后缀算式为_______________________________。 5. 5. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n 个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 6. 6. 对于一个具有n 个顶点和e 条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_______个和________个。 7. 7. AOV 网是一种___________________的图。 8. 8. 在一个具有n 个顶点的无向完全图中，包含有________条边，在一个具有n 个顶点的有向完全图中，包含有________条边。 9. 9. 假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为 一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 10. 10. 向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度 ___________。 11. 11. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的 时间复杂度为________。 12. 12. 在快速排序、堆排序、归并排序中，_________排序是稳定的。 三、 三、 运算题（每题 6 分，共24分） 1. 1. 在如下数组A 中链接存储了一个线性表，表头指针为A [0].next ，试写出该线性表。 A 0 1 2 3 4 5 6 7 data 60 50 78 90 34 40 next 3 5 7 2 4 1 2. 2. 请画出图10的邻接矩阵和邻接表。 3. 3. 已知一个图的顶点集V 和边集E 分别为： V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到 的各条边。 4. 4. 画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。 四、 四、 阅读算法（每题7分，共 14分） 1. 1. LinkList mynote(LinkList L) {//L 是不带头结点的单链表的头指针 if(L&&L->next){ q=L ；L=L －>next ；p=L ； S1： while(p －>next) p=p －>next ； S2： p －>next=q ；q －>next=NULL ； } 图10 return L； } 请回答下列问题： （1）说明语句S1的功能； （2）说明语句组S2的功能； （3）设链表表示的线性表为（a1,a2, …,a n）,写出算法执行后的返回值所表示的线性表。 2. 2.void ABC(BTNode * BT) { if BT { ABC (BT->left); ABC (BT->right); cout< } } 该算法的功能是： 五、五、算法填空（共8分） 二叉搜索树的查找——递归算法: bool Find(BTreeNode* BST,ElemType& item) { if (BST==NULL) return false; //查找失败 else { if (item==BST->data){ item=BST->data;//查找成功 return ___________;} else if(item return Find(______________,item); else return Find(_______________,item); }//if } 六、六、编写算法（共8分） 统计出单链表HL中结点的值等于给定值X的结点数。 int CountX(LNode* HL,ElemType x) 参考答案 一、一、单选题（每题2分，共20分） 1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A 二、二、填空题（每空1分，共26分） 1. 1.正确性易读性强壮性高效率 2. 2.O(n) 3. 3.9 3 3 4. 4.-1 3 4 X * + 2 Y * 3 / - 5. 5. 2n n-1 n+1 6. 6. e 2e 7. 7. 有向无回路 8. 8. n(n-1)/2 n(n-1) 9. 9. （12，40） （ ） （74） （23,55，63） 10. 10. 增加1 11. 11. O(log 2n) O(nlog 2n) 12. 12. 归并 三、 三、 运算题（每题6分，共24分） 1. 1. 线性表为：（78，50，40，60，34，90） 2. 2. 邻接矩阵：??? ? ????? ???????0111010101110111010101110 邻接表如图11所示： 图11 3. 3. 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 4. 4. 见图12 图12 四、 四、 阅读算法（每题7分，共14分） 1. 1. （1）查询链表的尾结点 （2）将第一个结点链接到链表的尾部，作为新的尾结点 （3）返回的线性表为（a 2,a 3,…,a n ,a 1） 2. 2. 递归地后序遍历链式存储的二叉树。 五、 五、 算法填空（每空2分，共8 分） true BST->left BST->right 六、 六、 编写算法（8分） int CountX(LNode* HL,ElemType x) { int i=0; LNode* p=HL;//i 为计数器 while(p!=NULL) { if (P->data==x) i++; p=p->next; }//while, 出循环时i 中的值即为x 结点个数 return i; }//CountX 4 4 4 4 4 2 2 2 5 5 5 2 2 8 8 4 3 5 2 8 3 4 一、 一、 单选题（每小题2分，共8分） 1、1、在一个长度为n 的顺序线性表中顺序查找值为x 的元素时，查找成功时的平均查找长度（即x 与 元素的平均比较次数，假定查找每个元素的概率都相等）为 ( )。 A n B n/2 C (n+1)/2 D (n-1)/2 2、2、在一个单链表中,若q 所指结点是p 所指结点的前驱结点,若在q 与p 之间插入一个s 所指的结点, 则执行( )。 A s →link=p →link; p →link=s; B p →link=s; s →link=q; C p →link=s →link; s →link=p; D q →link=s; s →link =p; 3、 3、 栈的插入和删除操作在（ ）进行。 A 栈顶 B 栈底 C 任意位置 D 指定位置 4、 4、 由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ） A 24 B 71 C 48 D 53 二、 二、 填空题（每空1分，共32分） 1、1、数据的逻辑结构被分为__________、 ___________ 、________和________四种。 2、2、一种抽象数据类型包括______________和_____________两个部分。 3、3、在下面的数组a 中链接存储着一个线性表，表头指针为a[o].next ，则该线性表为 _________________________________________________。 a 0 1 2 3 4 5 6 7 8 data next 4、4、在以HL 为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别 为________________和____________________。 5、5、用具有n 个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的 ___________，该循环队列的最大长度为__________。 6、6、当堆栈采用顺序存储结构时，栈顶元素的值可用———————表示；当堆栈采用链接存储 结构时，栈顶元素的值可用_______________表示。 7、7、一棵高度为5的二叉树中最少含有_________个结点，最多含有________个结点； 一棵高度为5的理想平衡树中，最少含有_________个结点，最多含有_________个结点。 8、8、在图的邻接表中，每个结点被称为____________，通常它包含三个域：一是_____________； 二是___________；三是_____________。 9、9、在一个索引文件的索引表中，每个索引项包含对应记录的_________和___________两项数据。 10、 10、 假定一棵树的广义表表示为A （B （C ，D （E ，F ，G ），H （I ，J ））），则树中所含 的结点数为_________个，树的深度为_________,树的度为________, 结点H 的双亲结点为________,孩子结点为_______________ 。 11、 11、 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_________,整个堆 排序过程的时间复杂度为________________。 12、 12、 在对m 阶的B_树插入元素的过程中，每向一个结点插入一个索引项（叶子结点中 的索引项为关键字和空指针）后，若该结点的索引项数等于______个，则必须把它分裂为_______ 60 56 42 38 74 25 4 3 7 6 2 0 1 个结点。 三、三、运算题（每小题6分，共24分） 1、1、已知一组记录的排序码为（46，79，56，38，40，80, 95，24），写出对其进行快速排序的 每一次划分结果。 2、2、一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散 列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。 3、3、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ，中序遍历的结果是EBCDAFHIGJ， 试写出这棵二叉树的后序遍历结果。 4、4、已知一个图的顶点集V各边集G如下： V = {0，1，2，3，4，5，6，7，8，9}； E = {（0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3 ，8），（5，6），（5，8），（5，9），（6， 7），（7，8），（8，9）} 当它用邻接矩阵表示和邻接表表示时，分别写出从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。 假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。 图深度优先序列广度优先序列 邻接矩阵表示时 邻接表表示时 四、四、阅读算法，回答问题（每小题8分，共16分） 1、假定从键盘上输入一批整数，依次为：78 63 45 30 91 34 –1，请写出输出结果。 # include < iostream.h> # include < stdlib.h > consst int stackmaxsize = 30; typedef int elemtype; struct stack { elemtype stack [stackmaxsize]; int top; }; # include “stack.h” V oid main ( ) { stack a; initstack(a); int x; cin >>x; while (x! = -1) { push (a, x ); cin >>x; } while (!stackempty (a)) cout < cout < } 该算法的输出结果为： __________________________________________________________. 2、阅读以下二叉树操作算法，指出该算法的功能。 Template unknown (BinTreeNode BinTreeNode< Type> *p =t, *temp; if (p!=NULL) { temp = p→leftchild; p→leftchild = p→rightchild; p→rightchild = temp; unknown(p→leftchild); undnown(p→rightchild); } } 该算法的功能是：________________________________ 五、五、算法填空，在画有横线的地方填写合适的内容（10分） 对顺序存储的有序表进行二分查找的递归算法。 int Binsch( ElemType A[ ],int low ,int high,KeyType K ) { if (low <= high) { int mid = 1 if ( K= = A[ mid ].key ) return mid; else if ( K < A[mid].key) return 2 else return 3 } else return 4 六、六、编写算法（10分） 编写算法，将一个结点类型为Lnode的单链表按逆序链接，即若原单链表中存储元素的次序为a1，......a n-1，a n，则逆序链接后变为, a n，a n-1， (1) V oid contrary (Lnode * & H L) 数据结构试题（答案） 一、单选题（每小题2分，共8分） 题号 1 2 3 4 答案 C D A B 二、填空题（每空1分，共32分） 1：集合、线性、树、图； 2：数据描述、操作声名； 3：（38，56，25，60，42，74）； 4：HL→next =NULL；HL=HL→next； 5：前一个位置；n-1； 6：S.stack [S.top]; HS→data; 7：5 31 8：边结点、邻接点域、权域、链域； 9：索引值域、开始位置域； 10：10、3、3、B、I和J； 11：O（log2n）、O(nlog2n); 12：m 、m - 1 三、运算题（每小题6分，共24分） 1、 划分次序划分结果 第一次[38 24 40] 46 [56 80 95 79] 第二次24 [38 40] 46 [56 80 95 79] 第三次24 38 40 46 [56 80 95 79] 第四次24 38 40 46 56 [80 95 79] 第五次24 38 40 46 56 79 [80 95] 第六次24 38 40 46 56 79 80 95 2、 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 查找成功的平均查找长度：ASL SUCC=14/10= 1.4 3、此二叉树的后序遍历结果是：EDCBIHJGFA 4、 图深度优先序列广度优先序列 四、阅读算法，回答问题（每小题8分，共 16分） 1、 1、 该算法的输入结果是：34 91 30 45 63 78 2、 2、 该算法的功能是：交换二叉树的左右子树的递归算法。 五、算法填空，在画有横线的地方填写合适的内容（10分） 1、1是：（low + high ）/2; 2是： Binsch(A,low,mid –1,K); 3是： Binsch(A,mid+1,high,K); 4是： -1； 六、编写算法（10分） 根据编程情况，酌情给分。 { Lnode *P=HL; HL=NULL; While (p!=null) { Lnode*q=p; P=p →next; q →next=HL; HL=q; } } 第一部分 选择题(30分) 一、一、项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个选 项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1．算法指的是（ ） A ．计算机程序 B ．解决问题的计算方法 C ．排序算法 D ．解决问题的有限运算序列 2．线性表采用链式存储时，结点的存储地址（ ） A ．必须是不连续的 B ．连续与否均可 C ．必须是连续的 D ．和头结点的存储地址相连续 3．将长度为n 的单链表链接在长度为m 的单链表之后的算法的时间复杂度为（ ） A ．O （1） B ．O （n ） C ．O （m ） D ．O （m+n ） 4．由两个栈共享一个向量空间的好处是：（ ） A ．减少存取时间，降低下溢发生的机率 B ．节省存储空间，降低上溢发生的机率 C ．减少存取时间，降低上溢发生的机率 D ．节省存储空间，降低下溢发生的机率 5．设数组data[m]作为循环队列SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作后其头指针front 值为（ ） A ．front=front+1 B ．front=(front+1)%(m-1) C ．front=(front-1)%m D ．front=(front+1)%m 6．如下陈述中正确的是（ ） 邻接矩阵表示时 0，1，2，8，3，4，5，6，7，9 0，1，4，2，7，3，8，6，5，9 邻接表表示时 0，4，3，8，9，5，6，7，1，2 0，4，1，3，7，2，8，6，9，5 A ．串是一种特殊的线性表 B ．串的长度必须大于零 C ．串中元素只能是字母 D ．空串就是空白串 7．若目标串的长度为n ，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是 （ ） A ．O （n 3） B ．O （n ） C ．O （n 2） D ．O （n 3） 8．一个非空广义表的表头（ ） A ．不可能是子表 B ．只能是子表 C ．只能是原子 D ．可以是子表或原子 9．假设以带行表的三元组表表示稀疏矩阵，则和下列行表 0 2 3 3 5 对应的稀疏矩阵是（ ） A.08067000000050400000-- ?????????? B.08 067000504000000300--?????? ??? ??????? C.08060000020050400000--?????????? ??? ? D .08060000700050 400300--???????????? ? ?? ? 10．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( ) A ．4 B ．5 C ．6 D ．7 11．在含n 个顶点和e 条边的无向图的邻接矩阵中,零元素的个数为( ) A ．e B ．2e C ．n 2－e D ．n 2－2e 12．假设一个有n 个顶点和e 条弧的有向图用邻接表表示,则删除与某个顶点v i 相关的所有弧的时间复杂 度是( ) A ．O(n) B ．O(e) C ．O(n+e) D ．O(n*e) 13．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化 情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（ ） A ．选择排序 B ．希尔排序 C ．归并排序 D ．快速排序 14．适于对动态查找表进行高效率查找的组织结构是（ ） A ．有序表 B ．分块有序表 C ．三叉排序树 D ．线性链表 15．不定长文件是指（ ） A ．文件的长度不固定 B ．记录的长度不固定 C ．字段的长度不固定 D ．关键字项的长度不固定 第二部分 非选择题（共70分） 二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）不写解答过程， 将正确的答案写在每小题的空格内。错填或不填均无分。 16．数据的逻辑结构是从逻辑关系上描述数据，它与数据的 无关，是独立于计算机的。 17．在一个带头结点的单循环链表中，p 指向尾结点的直接前驱，则指向头结点的指针head 可用p 表示为head= 。 18．栈顶的位置是随着 操作而变化的。 19．在串S=“structure ”中，以t 为首字符的子串有 个。 20．假设一个9阶的上三角矩阵A 按列优先顺序压缩存储在一维数组B 中，其中B[0]存储矩阵中第1 个元素a 1,1,则B[31]中存放的元素是 。 21．已知一棵完全二叉树中共有768结点，则该树中共有 个叶子结点。 22．已知一个图的广度优先生成树如右图所示，则与此相 应的广度优先遍历序列为 。 23．在单链表上难以实现的排序方法有 和 。 24．在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为 。 25．多重表文件和倒排文件都归属于 文件。 三、解答题（本大题共4小题，每小题5分，共20分） 26．画出下列广义表的共享结构图形表示 P=（（（z ）,(x,y)）,((x,y),x),(z)） 27．请画出与下列二叉树对应的森林。 28．已知一个无向图的顶点集为{a, b, c, d, e} ,其邻接矩阵如下所示 0100110010000110110110110???????? ???????? (1)画出该图的图形； （2）根据邻接矩阵从顶点a 出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。 29．已知一个散列表如下图所示： 35 20 33 48 59 0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函数为h(key)=key%13, 处理冲突的方法为双重散列法，探查序列为： h i =(h(key)+i *h1(key))%m i =0,1,…，m －1 其中 h1(key)=key%11+1 回答下列问题： （1）对表中关键字35，20，33和48进行查找时，所需进行的比较次数各为多少？ （2）该散列表在等概率查找时查找成功的平均查找长度为多少？ 四、算法阅读题（本大题共4小题，每小题5分，共20分） 30．下列算法的功能是比较两个链串的大小，其返回值为： comstr(s 1,s 2)=-<=>??? ? ?101121212当当当s s s s s s 请在空白处填入适当的内容。 int comstr(LinkString s1,LinkString s2) a b c d e 第一章绪论 1、数据结构是计算机中存储、组织数据的方式。精心选择的数据 结构可以带来最优效率的算法。 2、程序设计= 算法+数据结构 3、解决问题方法的效率： ●跟数据的组织方式有关 ●跟空间的利用效率有关 ●跟算法的巧妙程度有关 4、数据：所有能输入到计算机中,且被计算机处理的符号的集合， 是计算机操作对象的总称； 是计算机处理的信息的某种特定的符号表示形式。 5、数据元素：数据中的一个“个体”,数据结构中讨论的基本单 位。相当于“记录”,在计算机程序中通常作为一个整体考 虑和处理。 6、数据项: 相当于记录的“域”, 是数据的不可分割的最小单位, 如学号。数据元素是数据项的集合。 7、数据对象：性质相同的数据元素的集合. 例如: 所有运动员的记录集合 8、数据结构：是相互间存在某种关系的数据元素集合。 9、数据结构是带结构的数据元素的集合。 10、不同的关系构成不同的结构。 11、次序关系： { 1-1什么是数据? 它与信息是什么关系? 【解答】 什么是信息？广义地讲，信息就是消息。宇宙三要素（物质、能量、信息）之一。它是现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。 什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如，一个大楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。 1-2什么是数据结构? 有关数据结构的讨论涉及哪三个方面? 【解答】 数据结构是指数据以及相互之间的关系。记为：数据结构= { D, R }。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。 有关数据结构的讨论一般涉及以下三方面的内容： ①数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构； ②数据成员极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构； ③施加于该数据结构上的操作。 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。 1-3数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、 队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？ 【解答】 线性结构的特点是：在结构中所有数据成员都处于一个序列中，有且仅有一个开始成员和一个终端成员，并且所有数据成员都最多有一个直接前驱和一个直接后继。例如，一维数组、线性表等就是典型的线性结构 非线性结构的特点是：一个数据成员可能有零个、一个或多个直接前驱和直接后继。例如，树、图或网络等都是典型的非线性结构。 1-4．什么是抽象数据类型？试用C++的类声明定义“复数”的抽象数据类型。要求 (1) 在复数内部用浮点数定义它的实部和虚部。 (2) 实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。 (3) 定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。 第七章数据结构作业答案 第七章图 选择题 1．设无向图的顶点个数为n，则该图最多有（ B ）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 2．一个n个顶点的连通无向图，其边的个数至少为（ A ）。 A．n-1 B．n C．n+1 D．nlogn； 3．一个有n个结点的图，最少有（ B ）个连通分量，最多有（ D ）个连通分量。 A．0 B．1 C．n-1 D．n 4．在一个无向图中，所有顶点的度数之和等于所有边数（ B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。 A．1/2 B．2 C．1 D．4 5．下列哪一种图的邻接矩阵是对称矩阵？（ B ） A．有向图 B．无向图 C．AOV网 D．AOE网 6．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（ B ）。 A．∑ = n i j i A 1 ] ,[ B． [] ∑ = n 1 j j,i A C． ∑ = n i i j A 1 ] , [ D． ∑ = n i j i A 1 ] ,[ + [] ∑ = n 1 j i,j A 7．下面哪一方法可以判断出一个有向图是否有环（回路）：( B ) A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 广度优先遍历 8. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( B )。 A. O(n) B. O(n+e) C. O(n2) D. O(n3) 9. 求解最短路径的Floyd算法的时间复杂度为( D )。 A．O（n） B. O（n+c） C. O（n*n） D. O（n*n*n） 10．若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列（ A ）。 A．存在 B．不存在 11．一个有向无环图的拓扑排序序列（ B ）是唯一的。 A．一定 B．不一定 12. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ D ）。 A．G中有弧 一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N）的联系 时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是 ___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插 入元素的时间复杂度为____________。 5. 5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ， 则二维数组W的数据元素共占用＿_____＿个字节。W中第6 行的元素和第4 列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。 6. 6.广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。 7.7.二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结点的度的 总和是_____________。 8.8.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由算术表 达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。 2015年清华大学826运筹学与统计学（数学规划、应用随机模型、统计学各占1/3）考研复习参考书 科目：826 运筹学与统计学（数学规划、应用随机模型、统计学各占1/3）参考书：《运筹学（数学规划）（第3版）清华大学出版社，2004年1月 W.L.Winston 《运筹学》（应用随机模型）清华大学出版社，2004年2月 V.G. Kulkarni 《概率论与数理统计》（第1～9章）高等教育出版社，2001年盛聚等 考研复习方法，这里不详细展开。简单归纳为： 新祥旭考研提醒：首先，清楚考试明细，掌握真题，真题为本。通过真题，了解和熟知：考什么、怎么考、考了什么、没考什么；通过练习真题，了解：目前我的能力、复习过程中我的进步、我的考试目标。提醒一句：千万不要浪费大量时间做不相关的模拟题；千万不要把考研复习等同于做题目，搞题海战术。 其次，把握参考书，参考书为锚。弄懂、弄熟。考研复习如何才能成功？借用《卖油翁》里的一句话，那就是：手熟而已。明确考试之后，考研就基本上是一个熟悉吃透的过程。无论何时，参考书第一，不能轻视。所以，千万不要本末倒置，把做题凌驾于看书之上。如何才叫熟悉？我认为，要打破“讲速度，不讲效率”的做法，看了多少遍并不是检验熟悉与否的指标，合上书本，随时自我检测，能否心中有数、一问便知，这才是关键。 再次，制定计划，合理分配时间。不是每一本参考书都很重要，都一样重要，所以，在了解真题的基础上，要了解每一本书占多少分，如何命题考试，在此基础上，每一本参考书的主次轻重、复习方略也就清楚了，复习才不会像开摊卖药，平均用力。一个月制定一份计划书，每天写一句话鼓励自己，一个月调整一次复习重点，这都是必要的。 最后，快乐复习。考研复习是以什么样状态进行的，根源在于能否克服不良情绪。第一，报考对外汉语，你是因为喜欢这个专业吗？如果是，那么，就继续给自己这种暗示，那么你一定会发现，复习再紧张，也是愉悦的，因为你是为了兴趣而考研的；第二，规律的作息，不大时间战，消耗战，养精蓄锐。运动加休息，如果能每天都很规律，那么成功也就有了保障，负面情绪少了，效率也就高了。 总结为几个关键词，就是：知己知彼、本末分明。 李春葆编著：数据结构（C语言篇）――习题与解析（修订版） 清华大学出版社 一、绪论 选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。 1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。 A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面是2。 1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.正确性和简单性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。 A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。 A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表 C.栈的操作方式是先进先出 D.队列的操作方式是先进后出 10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。 A.正确 B.不正确 填空题 1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。 2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3.在树形结构中，树根结点没有结点，其余每个结点有且只有个前驱结点；叶子结点没有结点，其余每个结点的后续可以。 附录习题参考答案 习题1参考答案 1.1.选择题 (1). A. (2). A. (3). A. (4). B.,C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.) A. 1.2.填空题 (1). 数据关系 (2). 逻辑结构物理结构 (3). 线性数据结构树型结构图结构 (4). 顺序存储链式存储索引存储散列表（Hash）存储 (5). 变量的取值范围操作的类别 (6). 数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系 (7). 关系网状结构树结构 (8). 空间复杂度和时间复杂度 (9). 空间时间 (10). Ο(n) 1.3 名词解释如下： 数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。 数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。 数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。 数据类型：是指变量的取值范围和所能够进行的操作的总和。 算法：是对特定问题求解步骤的一种描述，是指令的有限序列。 1.4 语句的时间复杂度为： (1) Ο(n2) (2) Ο(n2) (3) Ο(n2) (4) Ο(n-1) (5) Ο(n3) 1.5 参考程序： main() { int X,Y,Z； scanf(“%d, %d, %d”,&X,&Y,Z)； if (X>=Y) if(X>=Z) if (Y>=Z) { printf(“%d, %d, %d”,X,Y,Z);} else { printf(“%d, %d, %d”,X,Z,Y);} 运筹学部分课后习题解答P47 1.1 用图解法求解线性规划问题 a） 12 12 12 12 min z=23 466 ..424 ,0 x x x x s t x x x x + +≥ ? ? +≥ ? ?≥ ? 解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都为 最优解，即该问题有无穷多最优解，这时的最优值为 min 3 z=2303 2 ?+?= P47 1.3 用图解法和单纯形法求解线性规划问题 a） 12 12 12 12 max z=10x5x 349 ..528 ,0 x x s t x x x x + +≤ ? ? +≤ ? ?≥ ? 解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点， 即 1 12 122 1 349 3 528 2 x x x x x x = ? += ?? ? ?? +== ?? ? ，即最优解为* 3 1, 2 T x ?? = ? ?? 这时的最优值为 max 335 z=1015 22 ?+?= 单纯形法： 原问题化成标准型为 121231241234 max z=10x 5x 349 ..528,,,0x x x s t x x x x x x x +++=?? ++=??≥? j c → 10 5 B C B X b 1x 2x 3x 4x 0 3x 9 3 4 1 0 0 4x 8 [5] 2 0 1 j j C Z - 10 5 0 0 0 3x 21/5 0 [14/5] 1 -3/5 10 1x 8/5 1 2/5 0 1/5 j j C Z - 1 0 - 2 5 2x 3/2 0 1 5/14 -3/14 10 1x 1 1 0 -1/7 2/7 j j C Z - -5/14 -25/14 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 9-12章数据结构作业答案 第九章查找 选择题 1、对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A ) A．（n+1）/2 B. n/2 C. n D. [（1+n）*n ]/2 2. 下面关于二分查找的叙述正确的是 ( D ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储 3. 二叉查找树的查找效率与二叉树的( （1）C)有关, 在 (（2)C ）时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 4. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）A) 个链表。 这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）C) （1） A．17 B. 13 C. 16 D. 任意 （2） A．0至17 B. 1至17 C. 0至16 D. 1至16 判断题 1．Hash表的平均查找长度与处理冲突的方法无关。 (错) 2. 若散列表的负载因子α<1，则可避免碰撞的产生。（错） 3. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（错） 填空题 1. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20， 需做的关键码比较次数为 4 . 算法应用题 1. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长 为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10解决冲突。要求：对该关 键字序列构造哈希表，并计算查找成功的平均查找长度。 2. 已知散列表的地址空间为A[0..11]，散列函数H（k）=k mod 11，采用线性探测法处理冲 突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在 等概率情况下查找成功时的平均查找长度。 ３、对长度为20 的有序表进行二分查找，试画出它的一棵判定树，并求等概率情况下的平均 查找长度。 ４、设散列表的长度为15，散列函数H（K）=K%13，给定的关键字序列为20，16，29，82，37，02，06，28，55，39，23，10，试写出分别用拉链法和线性探测法解决冲突时所构造的散 列表，并求出在等概率情况下，这两种方法查找成功时的平均查找长度。 运筹学模拟2 3分，共5题，总计15分） 1.线性规划问题中可行域的顶点与线性规划问题的（）对应。 A 可行解 B 基本解 C 基本可行解 D 不能确定 2．在对偶理论中下列说法正确的是：（） A 原问题任一可行解的目标函数值是其对偶问题目标函数值的上界。 B 对偶问题任一可行解的目标函数值是其原问题目标函数的下界。 C 如原问题有可行解且目标函数值无界，则其对偶问题无可行解 D 若原问题有可行解而其对偶问题无可行解，则原问题目标函数值有界。 3．资源的影子价格实际上是一种机会成本。在纯市场经济条件下，当市场价格低于影子价格时，这种资源应该：（） A买进 B卖出 C不买进也不卖出 D不能确定 4．关于整数线性规划问题与它的松弛问题之间的关系说法不正确的是：（）A整数线性规划问题的可行域是它的松弛问题可行域的子集。 B若松弛问题无可行解，则整数线性规划问题也无可行解 C松弛问题的最优解是整数线性规划问题的最优解的一个下界。 D若松弛问题的最优解的各个分量都是整数，则它也是整数线性规划的最优解 5．一个人的效用曲线反映了他对风险的态度。对实际收入的增加的反应比较迟钝的是（） A 保守型 B 中间型 C 冒险型 D 无法确定 2分，共5题，总计10分） 1．如果一个线性规划问题有可行解，那么它一定有最优解。（） 2．若线性规划的原问题和对偶问题都有最优解，则它们最优解一定相等。（） y>0,说明在最优生产计划中， 3．已知在线性规划的对偶问题的最优解中，对偶变量 i 第i种资源已经完全用尽。（） 4．因为运输问题是一种特殊的线性规划模型，因而求其解也可能出现下列4种情况：有唯一最优解，有无穷最优解，无界解，无可行解。（） 清华数据结构习题集答案(C语言版严蔚敏) 第1章绪论 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i为实数} 数据关系：R={ 数据结构》 、选择题 3给了一序列比如6.7.4.8.9.3. 散列函数是H(key)=key%11. 一问成功时的平均搜索长度二问不成功的平均搜索长度 哪种数据结构，从某一个结点到根结点的路径序列组成一个降序排列 a. b. 最大堆c. 最小堆d 还有一个题是关于关键路径的，答案选项是49 /B -C \ /F\ \ \D-E H \G/ 什么是数据结构？A B C定义在一个数据集合上的属性和操作D 高度为h的完全二叉树，一共有多少种？ A B 2A(h-1) 、证明题 1.什么样的有向无环图有唯一的拓扑有序序列，并证明。 三、计算题 1 有n 个结点的二叉树最大高度，最小高度分别是多少？ 2 一棵有n个结点的树有m个叶节点，如果用做兄弟-右子女表示法，则有多少个结点的右指针域为空? 3 霍夫曼树中，有n 个叶结点，问一共有多少个结点? 4有n 个结点的树的不同排列形式有多少种。 四、给定一个文件有1,000,000个记录，每个200B,记录中关键码大小50B,页面大小为 4kB,现以B+树(最大关键码复刻)方式组织该文件，尽量使每结点拥有尽可能多的关键码，已知每个指针占用5B。 问1.该B+树有多少个叶结点，共有多少层；2.该B+树共有多少个索 引结点；3. 每次搜索要读盘多少次？ 五、算法设计题 1. 给定A[n], 设计一个算法,重排数组,使得奇数都在数组前半部分,偶数都在后半部分。要求时间复杂度O(n) 。 函数头：void exstorage(int A[], int n) 2.重新设计一个直接选择算法函数，采用递归方式。对一个大小为n 的数组，初始的调用方式为：selectsort(A, 0, n-1) 。 函数头：void selectsort(int A[],int left, int right) 操作系统》 、简答题 1.磁盘I/O 操作的时间组成部分，阐述优化磁盘调度策略的目标。 2.什么是内碎片，外碎片。 2010年《数据结构》期终考试试卷（A） 班级学号姓名 一、简答题（每小题6分，共30分） (1) 假设一个线性链表的类名为linkedList，链表结点的类名为ListNode，它包含两个数据成员data和link。data存储该结点的数据，link是链接指针。下面给定一段递归打印一个链表中所有结点中数据的算法： void PrintList (ListNode *L) { if ( L != NULL ) { cout << L->data << endl; PrintList ( L->link ); } } 试问此程序在什么情况下不实用？给出具体修改后的可实用的程序？ (1) 此程序在内存容量不足时不适用。因为需要一个递归工作栈。当链表越长，递归工作栈的深度越深，需要的存储越多。可采用非递归算法节省存储。 void PrintList (ListNode *L) { while ( L != NULL ) { cout << L->data << endl; L = L->link; } } (2) 如果每个结点占用2个磁盘块因而需要2次磁盘访问才能实现读写，那么在一棵有n个关键码的2m阶B树中，每次搜索需要的最大磁盘访问次数是多少？ (2) 在2m阶B树中关键码个数n与B树高度h之间的关系为h≤log m ((n+1)/2)+1，那么每次搜索最大磁盘访问次数为2h max = 2log m ((n+1)/2)+2。 (3) 给定一棵保存有n 个关键码的m 阶B 树。从某一非叶结点中删除一个关键码需要的最大磁盘访问次数是多少？ (3) 在m 阶B 树中关键码个数n 与B 树最大高度h 的关系为h = log ?m/2?((n+1)/2)+1。若设寻找被删关键码所在非叶结点读盘次数为h ’，被删关键码是结点中的k i ，则从该结点的p i 出发沿最左链到叶结点的读盘次数为h -h ’。当把问题转化为删除叶结点的k 0时，可能会引起结点的调整或合并。极端情况是从叶结点到根结点的路径上所有结点都要调整，除根结点外每一层读入1个兄弟结点，写出2个结点，根结点写出1个结点，假设内存有足够空间，搜索时读入的盘块仍然保存在内存，则结点调整时共读写盘3(h -1)+1。总共的磁盘访问次数为 h ’+(h -h ’)+3(h -1)+1 = 4h -2 = 4(log ?m/2?((n+1)/2)+1)-2 = = 4log ?m/2?((n+1)/2)+2 (4) 给定一个有n 个数据元素的序列，各元素的值随机分布。若要将该序列的数据调整成为一个堆，那么需要执行的数据比较次数最多是多少？ (4) 设堆的高度为h = ?log 2(n+1)?，当每次调用siftDown 算法时都要从子树的根结点调整到叶结点，假设某子树的根在第i 层（1≤i ≤h -1），第h 层的叶结点不参加比较。从子树根结点到叶结点需要比较h -i 层，每层需要2次比较：横向在两个子女里选一个，再纵向做父子结点的比较。因此，在堆中总的比较次数为 )i h j ( 2j 2 2j 22 2j 2 2)i h (221 h 1 j j 1 -h 1 h 1 j j -1 h 1 h 1 j 1 -j -h 1h 1 i 1-i -=??=??=?=-∑ ∑∑∑-=-=--=-=代换 因为 2h-1 ≤n ≤2h -1，且∑-=∞ →=1 h 1j j h 22j lim ，则n 42n 22 j 221 h 1j j 1 h =??≤??∑-=- 1.16 void print_descending(int x,int y,int z)//按从大到小顺序输出三个数 { scanf("%d,%d,%d",&x,&y,&z); if(x 《运筹学》试题（答案） 一、单项选择题。下列每题给出的四个答案中只有一个是正确的，将表示正确答案的字母填入题后的括号中。（20分） 1．对一个极大化的线性规划问题用单纯形法求解，若对所有的检验数0 ≤j σ，但对某个 非基变量j x ，有0 =j σ，则该线性规划问题（ B ） A ．有唯一的最优解； B ．有无穷多个最优解； C ．为无界解； D ．无可行解。 2．使用人工变量法求解极大化线性规划问题时，当所有的检验数0 ≤j σ，在基变量中仍含有非零的人工变量，表明该线性规划问题（ D ） A ．有唯一的最优解； B ．有无穷多个最优解； C ．为无界解； D ．无可行解。 3．在对偶问题中，若原问题与对偶问题均具有可行解，则（ A ） A ．两者均具有最优解，且它们最优解的目标函数值相等； B ．两者均具有最优解，原问题最优解的目标函数值小于对偶问题最优解的目标函数值； C ．若原问题有无界解，则对偶问题无最优解； D ．若原问题有无穷多个最优解，则对偶问题只有唯一最优解； 4．在用对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中（ D ） A ．b 列元素不小于零； B ．检验数都大于零； C ．检验数都不小于零； D ．检验数都不大于零。 5．在产销平衡运输问题中，设产地为m 个，销地为n 个，那么解中非零变量的个数（ A ）。 A ．不能大于(m +n -1)；B ．不能小于(m +n -1)；C ．等于(m +n -1)；D ．不确定。 6．在运输问题中，每次迭代时，如果有某非基变量的检验数等于零，则该运输问题（ B ）。 A ．无最优解；B ．有无穷多个最优解；C ．有唯一最优解；D ．出现退化解。 7．在目标规划中，求解的基本原则是首先满足高级别的目标，但当高级别目标不能满足时（ D ）。 A ．其后的所有低级别目标一定不能被满足； B ．其后的所有低级别目标一定能被满足； C ．其后的某些低级别目标一定不能被满足； D ．其后的某些低级别目标有可能被满足。 8．若一个指派问题的系数矩阵的某行各元素都加上常数k 得到一个新的矩阵，这一新矩阵对应着一个新的指派问题，则（ A ）。 A ．新问题与原问题有相同的最优解； B ．新问题最优目标值大于原问题最优目标函数值； C ．新问题最优解等于原问题最优解加上k ； D ．新问题最优解小于原问题最优解。 9．如果要使目标规划实际实现值不超过目标值，则相应的偏离变量应满足（ B ）。 A ．0>+d ； B ．0=+d ； C ．0=-d ； D ． .0,0>>+-d d 10．动态规划问题中最优策略具有性质：（ C ） A ．每个阶段的决策都是最优的； B ．当前阶段以前的各阶段决策是最优的； C ．无论初始状态与初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应 清华数据结构习题集答案(C 语言版严蔚敏) 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 3.7 习题 3.7.1知识点：栈的基本概念 一、选择题 1①下列哪种数据结构常用于函数调用（A ）。 Ａ．栈Ｂ．队列Ｃ．链表Ｄ．数组 2①编译器中通常以哪种数据结构处理递归程序调用（C ） Ａ．队列Ｂ．数组 C．栈 D．记录 3①下列哪些数据结构可用来实现栈（D ）。 （1）链表（2）数组（3）树（4）图 Ａ．（2），（3）Ｂ．（2），（4） C．（1），（4） D．（1），（2）4②元素的入栈序列是a,b,c,d，则栈的不可能的输出序列是（ C ）。 A．dcba B．abcd C．dcab D．cbad 5②已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（C）。 A．5，4，3，2，1，6 B．2，3，5，6，1，4 C．3，2，5，4，1，6 D．1，4，6，5，2，3 6②若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（ D ）。 A．SXSSXXXX B．SXXSXSSX C．SXSXXSSX D．SSSXXSXX 7①对于栈操作数据的原则是（B ）。【青岛大学2001】 A．先进先出 B．后进先出 C．后进后出 D．不分顺序 8①栈在（ D ）中应用。【中山大学1998】 A．递归调用 B．子程序调用 C．表达式求值 D．A，Ｂ，Ｃ9②一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（B ）。【中山大学1999】 A．不确定 B．n-i+1 C．i D．n-i 10②若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j 个输出元素是（D ）。【武汉大学2000】 A．i-j-1 B．i-j C．j-i+1 D．不确定的 11②有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ C ）【北方交通大学2001】 A．5 4 3 6 1 2 B．4 5 3 1 2 6 C．3 4 6 5 2 1 D．2 3 4 1 5 6 12②输入序列为ABC，可以变为CBA 时，经过的栈操作为（B ）【中山大学1999】A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,pop数据结构 清华大学出版社 严蔚敏吴伟民编著
数据结构课后习题答案清华大学出版社殷人昆
数据结构(C语言版)第7章练习 答案 清华大学出版社
清华大学数据结构试题及答案
2015年清华大学826运筹学与统计学
李春葆数据结构习题与解析(修订版)知识分享
数据结构(C语言版)第三版__清华大学出版社_习题参考答案
第四版运筹学部分课后习题解答
最新数据结构习题集答案解析--清华大学版
数据结构(C语言版)9-12章练习 答案 清华大学出版社
运筹学模拟卷2运筹学胡运权清华大学出版社
清华数据结构习题集答案(C语言版严蔚敏)
清华08计算机考研试题
《数据结构》期终考试试卷(A)-清华大学
数据结构习题集答案(c版)(清华大学 严蔚敏)
运筹学教程第五版课后答案
清华大数据结构习题集问题详解(C语言版严蔚敏)
大连东软数据结构题库全3
相关主题
文本预览