2021年数据结构C语言版期末题库.doc

“数据构造”期末考试试题一、单选题(每小题2分，共12分)1在一种单链表HL中，若要向表头插入一种由指针p指向结点，则执行( )。A HLps p一nextHLB p一nextHL；HLp3C p一nextHl；pHL；D p一nextHL一next;HL一nextp；2n个顶点强连通图中至少具有( )。A.nl条有向边 B.n条有向边C.n(n1)2条有向边 D.n(n一1)条有向边3.从一棵二叉搜索树中查找一种元素时，其时间复杂度大体为( )。A.O(1) B.O(n)C.O(1Ogzn) D.O(n2)4由权值分别为3，8，6，2，5叶子结点生成一棵哈夫曼树，它带权途径长度为( )。A24 B48C 72 D 535当一种作为实际传递对象占用存储空间较大并也许需要修改时，应最佳把它阐明为( )参数，以节约参数值传播时间和存储参数空间。A.整形 B.引用型C.指针型 D.常值引用型6向一种长度为n顺序表中插人一种新元素平均时间复杂度为( )。AO(n) BO(1)CO(n2) DO(10g2n)二、填空题(每空1分，共28分)1数据存储构造被分为、和四种。2在广义表存储构造中，单元素结点与表元素结点有一种域相应不同，各自分别为域和域。3中缀表达式 3十x*(2.456)所相应后缀表达式为。4在一棵高度为h3叉树中，最多具有结点。5假定一棵二叉树结点数为18，则它最小深度为，最大深度为6在一棵二叉搜索树中，每个分支结点左子树上所有结点值一定该结点值，右子树上所有结点值一定该结点值。7当向一种小根堆插入一种具备最小值元素时，该元素需要逐级调节，直到被调节到位置为止。8表达图三种存储构造为、和。9对用邻接矩阵表达具备n个顶点和e条边图进行任一种遍历时，其时间复杂度为，对用邻接表表达图进行任一种遍历时，其时间复杂度为。10从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为和11假定对长度n144线性表进行索引顺序查找，并假定每个子表长度均为，则进行索引顺序查找平均查找长度为，时间复杂度为12一棵B树中所有叶子结点均处在上。13每次从无序表中顺序取出一种元素，把这插入到有序表中恰当位置，此种排序办法叫做排序；每次从无序表中挑选出一种最小或最大元素，把它互换到有序表一端，此种排序办法叫做排序。14迅速排序在乎均状况下时间复杂度为，最坏状况下时间复杂度为。三、运算题(每小题6分，共24分)1假定一棵二叉树广义表表达为a(b(c，d)，c(，8)，分别写出对它进行先序、中序、后序和后序遍历成果。先序：中序；后序：2已知一种带权图顶点集V和边集G分别为：V0，1，2，3，4，5；E=(0，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)25，(2，4)13，(3，5)9，(4，5)10， 则求出该图最小生成树权。最小生成树权；3假定一组记录排序码为(46，79，56，38，40，84，50，42)，则运用堆排序办法建立初始堆为。4有7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点生成一棵哈夫曼树，求出该树带权途径长度、高度、双分支结点数。带权途径长度： 高度： 双分支结点数：。四、阅读算法，回答问题(每小题8分，共16分)1VOldAC(List&L)InitList(L)；InsertRear(L;25)；InsertFront(L，50)；IntaL45，8，12，15，36;for(inti0；i5；i+)if (ai20)InsertFront(L，ai)；elselnsertRear(L，ai)；该算法被调用执行后，得到线性表L为：2void AG(Queue&Q)InitQueue(Q)；inta56，12，5，15，8；for(int i0;i5；i+)QInsert(Q，ai)；QInsert(Q，QDelete(Q)；QInsert(Q，20)；QInsert(Q，QDelete(Q)十16)；while(!QueueEmpty(Q)coutQDelete(Q)”；该算法被调用后得到输出成果为：五、算法填空，在画有横线地方填写适当内容(每小题6分，共12分)1从一维数组An)中二分查找核心字为K元素递归算法，若查找成功则返回相应元素下标，否则返回一1。IntBinsch(ElemTypeA，Intlow，int high，KeyTypeK)if(lowhigh)int mid(low+high)2；if(KAmid.key)；else if (KdataX)return 1；根结点层号为1向子树中查找x结点elseint clNodeLevel(BT一left，X)；if(cl1)return cl+1;int c2 ；if；若树中不存在X结点则返回oelse return 0；六、编写算法(8分)按所给函数声明编写一种算法，从表头指针为HL单链表中查找出具备最大值结点，该最大值由函数返回，若单链表为空则中断运营。EIemType MaxValue(LNOde*HL);“数据构造”期末考试试题答案一、单选题(每小题2分，共12分)评分原则；选对者得2分，否则不得分。1B 2B 3C 4D 5B 6A二、填空题(每空1分，共28分)1顺序构造 链接构造 索引构造 散列构造(顺序无先后)2值(或data) 子表指针(或sublist)33 x 24 56一*十4(3h一1)25 5 186不大于 不不大于(或不不大于等于)7向上 堆顶8邻接矩阵 邻接表 边集数组(顺序无先后)9O(n2) O(e)10 1 31113 O()12同一层13插人 选取14O(nlog2n) O(n2)三、运算题(每小题6分，共24分)1先序：a，b，c，d，e，f，e 2分中序：c，b，d，a，f，8，e 2分后序：c，d，b，e，f，e，a 2分2最小生成树权：31 6分3(84，79，56，42，40，46，50，38) 6分4带权途径长度：131 3分高度：5 2分双分支结点数：6 1分四、阅读算法，回答问题(每小题8分，共16分)评分原则：每小题对的得8分，浮现一处错误扣4分，两处及以上错误不得分。1(36，12，8，50，25，5，15)25 15 8 6 20 28五、算法填空，在画有横线地方填写适当内容(每小题6分，共12分)1feturn mid 2分returnBinsch(A，low，mid一1，K) 2分returnBmsch(A，mid+1，high，K) 2分2NodeLevel(BT一right，X) 3分(c2=1)returnc2十1 3分六、编写算法(8分)评分原则：请参照语句后注释，或依照状况酌情给分。ElemType MaxValue(LNodeO* HL。)if (HL=NUlL) 2分cerrLinked llst is empty!”data； 3分LNOde*p=HI一next； 4分while(P!：NULL) 7分if(maxdata)maxp一data；pp一next；returnmax； 8分数据构造复习资料一、填空题1. 数据构造是一门研究非数值计算程序设计问题中计算机 操作对象 以及它们之间 关系 和运算等学科。2. 数据构造被形式地定义为（D，R），其中D是 数据元素 有限集合，R是D上 关系 有限集合。3. 数据构造涉及数据 逻辑构造 、数据 存储构造 和数据 运算 这三个方面内容。4. 数据构造按逻辑构造可分为两大类，它们分别是 线性构造 和 非线性构造 。5. 线性构造中元素之间存在一对一关系，树形构造中元素之间存在一对多关系，图形构造中元素之间存在多对多关系。6 在线性构造中，第一种结点 没有 前驱结点，别的每个结点有且只有 1个前驱结点；最后一种结点 没有 后续结点，别的每个结点有且只有1个后续结点。7. 在树形构造中，树根结点没有 前驱 结点，别的每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，别的每个结点后续结点数可以任意各种 。8. 在图形构造中，每个结点前驱结点数和后续结点数可以 任意各种 。9数据存储构造可用四种基本存储办法表达，它们分别是顺序 、链式 、索引 和 散列 。10. 数据运算最惯用有5种，它们分别是插入 、删除、修改、查找 、排序。11. 一种算法效率可分为 时间 效率和 空间 效率。12. 在顺序表中插入或删除一种元素，需要平均移动 表中一半元素，详细移动元素个数与 表长和该元素在表中位置 关于。13. 线性表中结点集合是 有限 ，结点间关系是 一对一 。14. 向一种长度为n向量第i个元素(1in+1)之前插入一种元素时，需向后移动 n-i+1 个元素。15. 向一种长度为n向量中删除第i个元素(1in)时，需向前移动 n-i 个元素。16. 在顺序表中访问任意一结点时间复杂度均为 O(1) ，因而，顺序表也称为 随机存取 数据构造。17. 顺序表中逻辑上相邻元素物理位置 必然相邻。单链表中逻辑上相邻元素物理位置 不一定 相邻。18在单链表中，除了首元结点外，任一结点存储位置由 其直接前驱结点链域值 批示。19 在n个结点单链表中要删除已知结点*p，需找到它前驱结点地址，其时间复杂度为O（n）。20. 向量、栈和队列都是 线性 构造，可以在向量 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。21. 栈是一种特殊线性表，容许插入和删除运算一端称为 栈顶 。不容许插入和删除运算一端称为 栈底 。22. 队列 是被限定为只能在表一端进行插入运算，在表另一端进行删除运算线性表。23. 不包括任何字符（长度为0）串 称为空串； 由一种或各种空格（仅由空格符）构成串 称为空白串。24. 子串定位运算称为串模式匹配； 被匹配主串 称为目的串， 子串 称为模式。25. 假设有二维数组A68，每个元素用相邻6个字节存储，存储器按字节编址。已知A起始存储位置（基地址）为1000，则数组A体积（存储量）为 288 B ；末尾元素A57第一种字节地址为 1282 ；若按行存储时，元素A14第一种字节地址为 (8+4)6+1000=1072 ；若按列存储时，元素A47第一种字节地址为 (674)61000）1276 。26 由个结点所构成二叉树有 5 种形态。27. 一棵深度为6满二叉树有 n1+n2=0+ n2= n0-1=31 个分支结点和 26-1 =32 个叶子。注：满二叉树没有度为1结点，因此分支结点数就是二度结点数。28 一棵具备个结点完全二叉树，它深度为 9 。（ 注：用 log2(n) +1= 8.xx +1=929设一棵完全二叉树有700个结点，则共有 350 个叶子结点。答：最快办法：用叶子数n/235030 设一棵完全二叉树具备1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。 答：最快办法：用叶子数n/2500 ，n2=n0-1=499。 此外，最后一结点为2i属于左叶子，右叶子是空，因此有1个非空左子树。完全二叉树特点决定不也许有左空右不空状况，因此非空右子树数0.31在数据存储无规律而言线性表中进行检索最佳办法是 顺序查找（线性查找） 。32. 线性有序表（a1，a2，a3，a256)是从小到大排列，对一种给定值k，用二分法检索表中与k相等元素，在查找不成功状况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。33. 假设在有序线性表a20上进行折半查找，则比较一次查找成功结点数为1；比较两次查找成功结点数为 2 ；比较四次查找成功结点数为 8 ；平均查找长度为 3.7 。 解：显然，平均查找长度O（log2n）top0 ST-top=0 ST-topm0 ST-top=m0（ C ）18. 在一种图中，所有顶点度数之和等于图边数 倍。A1/2 B. 1 C. 2 D. 4（ B ）19. 在一种有向图中，所有顶点入度之和等于所有顶点出度之和 倍。A1/2 B. 1 C. 2 D. 4（ B ）20. 有8个结点无向图最多有 条边。A14 B. 28 C. 56 D. 112 （ C ）21. 有8个结点有向完全图有 条边。A14 B. 28 C. 56 D. 112 （ B ）22在表长为链表中进行线性查找，它平均查找长度为. ；. （）;. ；. （）（ A ）23折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中 比较大小，查找成果是失败。A20，70，30，50 B30，88，70，50 C20，50 D30，88，50（ C ）24对22个记录有序表作折半查找，当查找失败时，至少需要比较 次核心字。A3 B4 C5 D 6（ A ）25. 链表合用于 查找A顺序 B二分法 C顺序，也能二分法 D随机数据构造与算法复习题一、选取题。1在数据构造中，从逻辑上可以把数据构造分为 C 。A动态构造和静态构造 B紧凑构造和非紧凑构造C线性构造和非线性构造 D内部构造和外部构造2数据构造在计算机内存中表达是指 A 。A数据存储构造 B数据构造 C数据逻辑构造 D数据元素之间关系3在数据构造中，与所使用计算机无关是数据 A 构造。A逻辑 B存储 C逻辑和存储 D物理4在存储数据时，普通不但要存储各数据元素值，并且还要存储 C 。A数据解决办法 B数据元素类型C数据元素之间关系 D数据存储办法5在决定选用何种存储构造时，普通不考虑 A 。A各结点值如何 B结点个数多少C对数据有哪些运算 D所用编程语言实现这种构造与否以便。6如下说法对的是 D 。A数据项是数据基本单位B数据元素是数据最小单位C数据构造是带构造数据项集合D某些表面上很不相似数据可以有相似逻辑构造7算法分析目是 C ，算法分析两个重要方面是 A 。（1）A找出数据构造合理性 B研究算法中输入和输出关系C分析算法效率以求改进 C分析算法易读性和文档性（2）A空间复杂度和时间复杂度 B对的性和简要性C可读性和文档性 D数据复杂性和程序复杂性8下面程序段时间复杂度是 O(n2) 。s =0;for( I =0；in；i+)for(j=0;jn;j+)s +=Bij;sum = s ;9下面程序段时间复杂度是 O(n*m) 。for( i =0；in；i+)for(j=0;jm;j+)Aij 0;10下面程序段时间复杂度是 O(log3n) 。i 0；while（inext =NULLChead-next =head D head!=NULL15带头结点单链表head为空鉴定条件是 B 。Ahead = NULL B head-next =NULLChead-next =head D head!=NULL16若某表最惯用操作是在最后一种结点之后插入一种结点或删除最后一种结点，则采用 D 存储方式最节约运算时间。A单链表 B给出表头指针单循环链表 C双链表 D带头结点双循环链表17需要分派较大空间，插入和删除不需要移动元素线性表，其存储构造是 B 。A单链表 B静态链表 C线性链表 D顺序存储构造18非空循环单链表head尾结点（由p所指向）满足 C 。Ap-next = NULL Bp = NULLCp-next =head Dp = head19在循环双链表p所指结点之前插入s所指结点操作是 D 。Ap-prior = s；s-next = p；p-prior-next = s；s-prior = p-priorBp-prior = s；p-prior-next = s；s-next = p；s-prior = p-priorCs-next = p；s-prior = p-prior；p-prior = s；p-prior-next = sDs-next = p；s-prior = p-prior；p-prior-next = s；p-prior = s20如果最惯用操作是取第i个结点及其前驱，则采用 D 存储方式最节约时间。A单链表 B双链表 C单循环链表 D 顺序表21在一种具备n个结点有序单链表中插入一种新结点并依然保持有序时间复杂度是 B 。AO（1） BO（n） CO（n2） DO（nlog2n）22在一种长度为n（n1）单链表上，设有头和尾两个指针，执行 B 操作与链表长度关于。A删除单链表中第一种元素B删除单链表中最后一种元素C在单链表第一种元素前插入一种新元素D在单链表最后一种元素后插入一种新元素23与单链表相比，双链表长处之一是 D 。A插入、删除操作更简朴B可以进行随机访问C可以省略表头指针或表尾指针D顺序访问相邻结点更灵活24如果对线性表操作只有两种，即删除第一种元素，在最后一种元素背面插入新元素，则最佳使用 B 。A只有表头指针没有表尾指针循环单链表B只有表尾指针没有表头指针循环单链表C非循环双链表D循环双链表25在长度为n顺序表第i个位置上插入一种元素（1 i n+1），元素移动次数为： A 。An i + 1 Bn i Ci Di 126对于只在表首、尾两端进行插入操作线性表，宜采用存储构造为 C 。A顺序表 B 用头指针表达循环单链表C用尾指针表达循环单链表 D单链表27下述哪一条是顺序存储构造长处？ C 。A插入运算以便 B可以便地用于各种逻辑构造存储表达C存储密度大 D删除运算以便28下面关于线性表论述中，错误是哪一种？ B 。A线性表采用顺序存储，必要占用一片持续存储单元B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链式存储，不必占用一片持续存储单元D线性表采用链式存储，便于进行插入和删除操作。29线性表是具备n个 B 有限序列。A字符 B数据元素 C数据项 D表元素30在n个结点线性表数组实现中，算法时间复杂度是O（1）操作是 A 。A访问第i（1=i=n）个结点和求第i个结点直接前驱（1i=n）B在第i（1=i=n）个结点后插入一种新结点C删除第i（1=inext=s；s-next=p-next B s-next=p-next ；p-next=s;Cp-next=s；p-next=s-next Dp-next=s-next；p-next=s36线性表顺序存储构造是一种 A 。A随机存取存储构造 B顺序存取存储构造C索引存取存储构造 DHash存取存储构造37栈特点是 B ，队列特点是 A 。A先进先出 B先进后出38栈和队列共同点是 C 。A都是先进后出 B都是先进先出C只容许在端点处插入和删除元素 D没有共同点39一种栈进栈序列是a，b，c，d，e，则栈不也许输出序列是 C 。Aedcba Bdecba Cdceab Dabcde40设有一种栈，元素依次进栈顺序为A、B、C、D、E。下列 C 是不也许出栈序列。AA,B,C,D,E BB,C,D,E,A CE,A,B,C,D DE,D,C,B,A41如下 B 不是队列基本运算？A从队尾插入一种新元素 B从队列中删除第i个元素C判断一种队列与否为空 D读取队头元素值42若已知一种栈进栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1n，则pi为 C 。Ai Bni Cni1 D不拟定43鉴定一种顺序栈st（最多元素为MaxSize）为空条件是 B 。Ast-top != -1 Bst-top = -1Cst-top != MaxSize D st-top = MaxSize44鉴定一种顺序栈st（最多元素为MaxSize）为满条件是 D 。Ast-top != -1 Bst-top = -1Cst-top != MaxSize Dst-top = MaxSize45一种队列入队序列是1，2，3，4，则队列输出序列是 B 。A4，3，2，1 B1，2，3，4C1，4，3，2 D3，2，4，146鉴定一种循环队列qu（最多元素为MaxSize）为空条件是 C 。Aqu-rear qu-front =MaxSize Bqu-rear qu-front -1=MaxSizeCqu-rear =qu-front D qu-rear =qu-front -147在循环队列中，若front与rear 分别表达对头元素和队尾元素位置，则判断循环队列空条件是 C 。Afront=rear+1 Brear=front+1 Cfront=rear Dfront=048向一种栈顶指针为h带头结点链栈中插入指针s所指结点时，应执行 D 操作。Ah-next=s ；Bs-next=h ;Cs-next=h ;h =s ；Ds-next=h-next ;h-next=s ;49输入序列为ABC，可以变为CBA时，通过栈操作为 B 。Apush，pop，push，pop，push，pop Bpush，push，push，pop， pop， popCpush，push，pop， pop，push，pop Dpush，pop，push，push，pop， pop50若栈采用顺序存储方式存储，现两栈共享空间V1 m，top1、top2分别代表第1和第2个栈栈顶，栈1底在V1，栈2底在Vm，则栈满条件是 B 。A|top2-top1|=0 B top1+1=top2 Ctop1+top2=mDtop1=top251设计一种鉴别表达式中左、右括号与否配对浮现算法，采用 D 数据构造最佳。A线性表顺序存储构