寻一份《数据结构》试题及答案
《数据结构》试题一、选择题（每小题2分，共30分）1． 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。A、单链表 B、双链表 C、单向循环 D、顺序表2． 串是任意有限个（ ）A、符号构成的序列 B、符号构成的集合C、字符构成的序列 D、字符构成的集合3． 设矩阵A（aij ，l≤i,j≤ 10）的元素满足：aij≠0(i≥j, l≤i, j≤ 10)aij=0 (i<j, l≤i, j≤ 10)现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A[9][5]的首址为A、2340 B、2336 C、2164 D、21604． 如果以链表作为栈的存储结构，则退栈操作时（ ）A、 必须判别栈是否满 B、 对栈不作任何判别C、 必须判别栈是否空 D、 判别栈元素的类型5． 设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（ ）A、front=front+1 B、front=(front+1)% mC、rear=(rear+1)%m D、front=(front+1)%(m+1)6． 深度为6（根的层次为1）的二叉树至多有（ ）结点。A、 64 B、32 C、31 D、637． 将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点X的双亲编号为（ ）A、24 B、25 C、23 D、无法确定8． 设有一个无向图G=（V，E）和G’=（V’，E’）如果G’为G的生成树，则下面不正确的说法是（ ）A、G’为G 的子图 B、G’为G 的边通分量C、G’为G的极小连通子图且V’=V D、G’为G的一个无环子图9． 用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（ ）A、 一定都是同义词 B、一定都不是同义词 C、都相同 D、不一定都是同义词10． 二分查找要求被查找的表是（ ）A、 键值有序的链接表 B、链接表但键值不一定有序C、 键值有序的顺序表 D、顺序表但键值不一定有序11． 当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（ ）A、n2 B、nlog2n C、log2n D、n-1 12． 堆是一个键值序列{k1,k2,…, kn},对i=1,2,…,|_n/2_|,满足( )A、ki≤k2i≤k2i+1 B、ki<k2i+1<k2iC、ki≤k2i且ki≤k2i+1(2i+1≤n) D、ki≤k2i 或ki≤k2i+1(2i+1≤n) 13．一个具有n个顶点的无向完全图的边数为（ ）A、n(n+1)/2 B、n(n-1)/2 C、n(n-1) D、n(n+1)14．在索引顺序表中查找一个元素，可用的且最快的方法是（ ）A、用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找B、用顺序查找法确定元素所在块，再用二分查找法在相应块中查找C、用二分查找法确定元素所在块，再用顺序查找法在相应块中查找D、用二分查找法确定元素所在块，再用二分查找法在相应块中查找15．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（ ）存储方式最节省运算时间。A、 单链表 B、双链表 C、带头结点的双循环链表 D、容量足够大的顺序表 二、判断题（每小题1分，共10分）1．双链表中至多只有一个结点的后继指针为空。（ ）2．在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。（ ）3．对链表进行插入和删除操作时，不必移动结点。（ ）4．栈可以作为实现程序设计语言过程调用时的一种数据结构。（ ）5．在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧<a,b>。( )i6．对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。( )7．“顺序查找法”是指在顺序表上进行查找的方法。（ ）8．向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（）9．键值序列{A，C，D，E，F，E，F}是一个堆。10．二路归并时，被归并的两个子序列中的关键字个数一定要相等。（） 三、填空题（每小题2分，共20分）1．在带有头结点的单链表L中，若要删除第一个结点，则需执行下列三条语句：＿＿＿＿＿＿＿＿；L->next=U->next；free(U)；2．有一个长度为20的有序表采用二分查找方法进行查找，共有＿＿＿＿＿＿个元素的查找长度为3。3．采用冒泡排序对有n个记录的表A按键值递增排序，若L的初始状态是按键值递增，则排序过程中记录的比较次数为＿＿＿＿＿。若A的初始状态为递减排列，则记录的交换次数为＿＿＿＿＿＿＿。4．在无头结点的双链表中，指针P所指结点是第一个结点的条件是＿＿＿＿＿＿。5．G为无向图，如果从G的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是＿＿＿＿＿图。6．如果一个有向图中没有＿＿＿＿＿＿，则该图的全部顶点可能排成一个拓扑序列。7．深度为8（根的层次号为1）的满二叉树有＿＿＿＿＿＿个叶子结点。 8．将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X，其双亲PARENT（X）的编号为＿＿＿＿＿＿＿。9．设某闭散列表HT未满，散列函数H（KEY）为键值第一字母在字母表中的序号，处理冲突方法为线性探测法，请在下列算法划线处填上适当内容，以实现按键值第一字母的顺序输出闭散列表中所有键值的算法。void printword(keytype HT[m]) { for(i=1;i<=26;i++) { j=i; while(____________________) { if (____________________) printf(“datatype”,HT[j]); j=(j+1)% m; } } }10．设有一个链队，结点结构为data|next，front为队头指针，rear为队尾指针，当执行入队操作时需执行下列语句：malloc(p)；p->data=x; p->next=NULL；＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿；＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿； 四、简答题：（每小题4分，共20分）1. 对于一个有10000个结点的二叉树，树叶最多有多少个？最少有多少个？2. 已知一棵二叉树的中序序列和后序序列分别为： DBGEACHF和DGEBHFCA，则该二叉树的前序序列是什么？3. 设有1000个无序的元素，需排出前10个最大（小）的元素，你认为采用哪种排序方法最快？为什么？4. 在KMP算法中，已知模式串为ADABCADADA ，请写出模式串的next[j]函数值。5. 中序遍历的递归算法平均空间复杂度为多少？ 五、 算法设计题（每小题10分，共20分）1. 试编写一个算法，判断一给定的整型数组a[n]是不是一个堆。2. 一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积。试写一高效算法，求二叉树的繁茂度。参考答案一、选择题1、D 2、C 3、D 4、C 5、D 6、D 7、A 8、B 9、D 10、C 11、D 12、C 13、B 14、C 15、D 二、判断题 1. √ 2. × 3. √ 4. √ 5. × 6. × 7. × 8. √ 9. √ 10. × 三、填空题1．U=L - > next2．4。 3．n-1、n(n-1)/2。4．p - > prior = NULL。5．连通6．回路或环7．28-1 = 27 = 1288．249．HT[j]!=NULL或HT[j]不为空、H(HT[j])=I10．rear - > next = p、rear = p四、简答题：1. 答： 最多是完全二叉树的形态，即5000个叶子；最少是单支树的形态，即1个叶子。2.答：是：ABDEGCFH3. 答：用锦标赛排序或堆排序很合适，因为不必等全部元素排完就能得到所需结果，时间效率为O(nlog2n)； 即O（1000log21000）=O(10000) 锦标赛排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089堆排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089若用冒泡排序也较快，最多耗费比较次数为（n-1+n-2+……＋n-10）=10n-55=10000-55=9945（次）4. 答： 01121123435. 答： 要考虑递归时占用了栈空间，但递归次数最多不超过树的高度，所以空间复杂度为O(log2n) 五、 算法设计题1.解：提示：堆的定义是：ki<k2i和K2i＋1 void SortA(sqlist &A, int n) { if(n==0) return(0); //空表if (a[1]<a[2]) { for( i=1; i<=n/2; i++) if (a[i]>a[2*i]|| a[i]>a[2*i+1])return(-1);return(minleap)};else { for( i=1; i<=n/2; i++) if (a[i]<a[2*i]|| a[i]<a[2*i+1])return(-1);return(“maxleap”)};}2. 要用层次遍历以及队列来处理，可以增设一个宽度计数器，在统计完每一层的结点个数之后,再从计数器中挑出最大值。typedef struct { BTNode node; int layer; //layer是结点所在层数 } BTNRecord, r ; int Width(Bitree T ){ //求树宽 int count[ ]; //增开count向量，存放各层对应的结点数 InitQueue(Q); //队列初始化，Q的元素为BTNRecord类型 EnQueue(Q,{T, 0}); //根结点入队, 0 表示count[0]，下标值 while(!QueueEmpty(Q)) { DeQueue(Q, r); //结点出队 count[r.layer]++; //出队时再把结点对应层的计数器加if(r.node->lchild) EnQueue(Q,{r.node->lchild, r.layer+1}); if(r.node->rchild) EnQueue(Q,{r.node->rchild, r.layer+1}); } //按层序入队时要随时标注结点所在层号 h=r.layer; //最后一个队列元素所在层就是树的高度 for(maxn=count[0], i=1; h; i++) if(count[i]>maxn) maxn=count[i]; //求出哪一层结点数最多 return (h*maxn)} // Width绛旓細2.Clifford A.Shaffer鍦銆婃暟鎹粨鏋涓庣畻娉曞垎鏋愩嬩竴涔︿腑鐨勫畾涔夋槸锛氣滄暟鎹粨鏋勬槸ADT锛堟娊璞℃暟鎹被鍨婣bstract Data Type锛 鐨勭墿鐞嗗疄鐜般傗3.Robert L.Kruse鍦ㄣ婃暟鎹粨鏋勪笌绋嬪簭璁捐銆嬩竴涔︿腑锛屽皢涓涓暟鎹粨鏋勭殑璁捐杩囩▼鍒嗘垚鎶借薄 灞傘佹暟鎹粨鏋勫眰鍜屽疄鐜板眰銆傚叾涓紝鎶借薄灞傛槸鎸囨娊璞℃暟鎹被鍨嬪眰锛屽畠璁ㄨ鏁版嵁鐨勯昏緫...
绛旓細銆婃暟鎹搴撱鏁版嵁缁撴瀯銆佽蒋浠跺伐绋嬭绋嬭璁℃寚瀵煎強涔犻瑙ｇ瓟銆嬫槸鐢辫蹇楁墠銆佹柟璐ゆ枃銆佸垬澹枩涓変綅浣滆呭叡鍚岀紪钁楃殑涓鏈暀鏉愩傝涔︾敱鍖椾含甯堣寖澶у鍑虹増闆嗗洟鍜屽畨寰藉ぇ瀛﹀嚭鐗堢ぞ鑱斿悎鍑虹増锛屽叾瀹樻柟鏍囪瘑涓篒SBN 9787566402714銆傝涔︾睄浜2011骞7鏈1鏃ラ娆″彂琛岋紝鏄涓鐗堢殑鍐呭銆傚叏涔﹀叡256椤碉紝閲囩敤骞宠鐗堝紡锛屽昂瀵镐负16寮锛岄傚悎瀛︿範鑰...
绛旓細鎺ㄨ崘浜2017-12-16 13:35:52 鏈浣绛旀 G.arcs[i][j]鍏跺疄灏辨槸涓涓偦鎺ョ煩闃典腑鐨勪竴涓暟,INFINITY鏄棤绌风殑鎰忔,澶ф鎰忔濆氨鏄畾涔夐《鐐筰鍒癹鏄笉杩為氱殑,鎵浠ュ害褰撶劧涓篘ULL浜嗐 涔︿笂绠楁硶瀹炵幇鐨勯棶棰,浣犲彧瑕佹湁C璇█鍩虹,鐒跺悗娉ㄦ剰姣忎釜C璇█鐨缁撴瀯浣撻渶瑕佸畾涔,杩樻湁灏辨槸涔︿笂鐨勭畻娉曞彧鏄竴涓嚱鏁,涓嶆槸涓诲嚱鏁,涓诲嚱鏁伴渶瑕...
绛旓細瑗跨澶т俊鎭粡娴庡鑰冭瘯闂绛旀 鎴戞潵绛 2涓洖绛 #娲诲姩# OPPO鎶ゅ睆璁″垝 3.0,鎹㈠睆5鎶樿捣! 鍖垮悕鐢ㄦ埛 2010-06-23 灞曞紑鍏ㄩ儴 绯荤粺:绯荤粺鏄敱澶勪簬涓瀹氱幆澧冧腑鐩镐簰鑱旂郴銆佺浉浜掍綔鐢ㄧ殑鑻ュ共缁勬垚閮ㄥ垎缁撳悎鑰屾垚骞朵负杈惧埌鏁翠綋鐩殑鑰屽瓨鍦ㄧ殑闆嗗悎銆備俊鎭郴缁:淇℃伅绯荤粺鏄竴涓汉閫犵郴缁,瀹冪敱浜恒佺‖浠躲佽蒋浠跺拰鏁版嵁璧勬簮缁勬垚,鐩殑鏄...
绛旓細銆傛垜鎺ㄨ崘缁欏ぇ瀹朵綔缁冧範鐢ㄧ殑鏁版嵁缁撴瀯缁冧範棰樻槸娓呭崕澶у涓ヨ敋鏁忚佸笀鐨勬暟鎹粨鏋勯闆嗐傝繖濂楅闆嗙殑C鐗绛旀鍦ㄦ湰绔欐湁璧勬枡涓嬭浇椤甸潰鍐呮湁涓嬭浇銆傝嚦浜庡涔犵敤鐨勬暀鏉愶紝渚濆悇涓鏍＄殑鎷涚敓绠绔犺屽畾锛屼笉杩囷紝澶у鏁板鏍￠噰鐢ㄧ殑鏄弗钄氭晱鐨勯偅鏈摑鑹叉垨缁胯壊鐨勬暟鎹粨鏋勬暀鏉愶紝钃濊壊鐨勬槸C鐗堬紝缁胯壊鐨勬槸PASCAL鐗堛
绛旓細Lobert L.Kruse 鍦銆婃暟鎹粨鏋涓庣▼搴忚璁°嬩竴涔︿腑,灏嗕竴涓暟鎹粨鏋勭殑璁捐杩囩▼鍒嗘垚鎶借薄灞傘佹暟鎹粨鏋勫眰鍜屽疄鐜板眰銆傚叾涓,鎶借薄灞傛槸鎸囨娊璞℃暟鎹被鍨嬪眰,瀹冭璁烘暟鎹殑閫昏緫缁撴瀯鍙婂叾杩愮畻,鏁版嵁缁撴瀯灞傚拰瀹炵幇灞傝璁轰竴涓暟鎹粨鏋勭殑琛ㄧず鍜屽湪璁＄畻鏈哄唴鐨勫瓨鍌ㄧ粏鑺備互鍙婅繍绠楃殑瀹炵幇銆 閲嶈鎰忎箟 涓鑸涓,涓涓暟鎹粨鏋勬槸鐢辨暟鎹厓绱犱緷鎹煇绉嶉昏緫...
绛旓細鈶舵爲鍨缁撴瀯銆傝缁撴瀯鐨鏁版嵁鍏冪礌涔嬮棿瀛樺湪鐫涓瀵瑰鐨勫叧绯汇傗懛鍥惧舰缁撴瀯銆傝缁撴瀯鐨勬暟鎹厓绱犱箣闂村瓨鍦ㄧ潃澶氬澶氱殑鍏崇郴锛屼篃绉扮綉鐘剁粨鏋勩8.瀵逛簬涓涓『瀵绘垬鏉ヨ,鎴樼┖ 鎴樻弧鐨勬潯浠:鏍堢┖鐨勬潯浠舵槸st->top=0,鏍堟弧鐨勬潯浠舵槸st->top==maxlen 9.N/2 10.杩涚▼姝婚攣鐨4涓〃瑕佹潯浠 锛1锛 浜掓枼鏉′欢锛氫竴涓祫婧愭瘡娆″彧鑳...
绛旓細鏃犻渶鍏堝缂栫▼璇█锛屽ぇ閮ㄥ垎涔︾睄鎻愪緵鐨勪唬鐮佺ず渚嬩粎闇鍩烘湰璇硶銆傝嫳璇笉浣宠呭彲浠ュ厛闃呰涓枃涔︾睄锛岄缈昏瘧璇剧▼璧勬枡锛屾參鎱㈤傚簲銆侰oursera璇剧▼璁块棶闂锛熻妫鏌NS璁剧疆锛屼笉涓瀹氶渶瑕佺炕澧欍傘婄畻娉 绗洓鐗堛嬭鍚庝範棰橀毦鎵捐В绛旓紵鍙互鍦ㄧ浉鍏宠鍧涘姹傚府鍔┿鏁版嵁缁撴瀯鐨勫涔犳槸涓涓寔缁殑杩囩▼锛屼繚鎸佺儹鎯呭拰鑰愬績锛屼綘浼氱湅鍒拌嚜宸辩殑鎴愰暱...
绛旓細浠讳綍涓滆タ閮芥槸鏈夌粨鏋勭殑瀵瑰惂锛鏁版嵁缁撴瀯灏辨槸鎶婃牴鎹暟鎹殑鐗圭偣銆佹ц川绛夊洜绱狅紝鎶婃ц川绫讳技鐨勬暟鎹粺涓璧锋潵锛屽苟涓斿畾涔変竴涓粨鏋勶紝姣斿绠鍗曠殑鏈夆滄暟缁勨濓紝澶嶆潅涓鐐圭殑鏈夌嚎鎬х粨鏋勨滄爤鈥濓紝鈥滈槦鍒椻濓紝闈炵嚎鎬х殑鏈夆滄爲鈥濓紝"鍥"锛岀瓑绛夈
