数据结构C语言版期末考试题附带复习资料.doc

- -“数据构造期末考试试题一、单项选择题(每题2分，共12分) 1在一个单链表HL中，假设要向表头插入一个由指针p指向的结点，那么执行( )。 A HLps p一nextHL B p一nextHL；HLp3 C 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在一棵高度为h的3叉树中，最多含有结点。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结点 else int clNodeLevel(BT一left，X)； if(cl1)return cl+1; int c2 ； if； 假设树中不存在X结点那么返回o else 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)2 5 5 18 6小于 大于(或大于等于) 7向上 堆顶 8邻接矩阵 邻接表 边集数组(次序无先后) 9O(n2) O(e) 10 1 3 1113 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，需找到它的前驱结点的地址，其时间复杂度为On。20. 向量、栈和队列都是 线性 构造，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。21. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。22. 队列是被限定为只能在表的一端进展插入运算，在表的另一端进展删除运算的线性表。23. 不包含任何字符长度为0的串称为空串； 由一个或多个空格仅由空格符组成的串称为空白串。24. 子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。25. 假设有二维数组A68，每个元素用相邻的6个字节存储，存储器按字节编址。A的起始存储位置基地址为1000，那么数组A的体积存储量为 288 B ；末尾元素A57的第一个字节地址为 1282 ；假设按行存储时，元素A14的第一个字节地址为 (8+4)6+1000=1072 ；假设按列存储时，元素A47的第一个字节地址为 (674)610001276 。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/2350 30 设一棵完全二叉树具有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。解：显然，平均查找长度Olog2ntop0 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 。1A找出数据构造的合理性 B研究算法中的输入和输出的关系C分析算法的效率以求改良 C分析算法的易读性和文档性2A空间复杂度和时间复杂度 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；whileinext =NULL Chead-next =head D head!=NULL15带头结点的单链表head为空的判定条件是 B 。Ahead = NULL B head-next =NULL Chead-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 。AO1 BOn COn2 DOnlog2n22在一个长度为nn1的单链表上，设有头和尾两个指针，执行 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 1 26对于只在表的首、尾两端进展插入操作的线性表，宜采用的存储构造为 C 。A顺序表 B 用头指针表示的循环单链表C用尾指针表示的循环单链表 D单链表27下述哪一条是顺序存储构造的优点？ C 。A插入运算方便 B可方便地用于各种逻辑构造的存储表示C存储密度大 D删除运算方便28下面关于线性表的表达中，错误的选项是哪一个？ B 。A线性表采用顺序存储，必须占用一片连续的存储单元B线性表采用顺序存储，便于进展插入和删除操作。