《数据结构》期末模拟试题二.doc

《数据结构》期末模拟试题二 一、单项选择题（每小题2分，共8分） 1．当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时，首先应执行（ ）语句修改top指针。 A．top++； B．top--； C．top=0； D．top； 2．从一个顺序存储的循环队列中删除一个元素时，首先需要（ ）。 A．队头指针加1 B．队头指针减1 C．取出队头指针所指的元素 D．取出队尾指针所指的元素 3．一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序（以位于最左位置的对象为基准）所得到的第一次划分结果为（ ）。 A．{38，46，79，56，40，84} B．{38，79，56，46，40，84} C．{40，38，46，79，56，84} D．{38，46，56，79，40，84} 4．某算法仅含并列的程序段1和程序段2，程序段1的执行次数3n2，程序段2的执行次数为0.01n3，则该算法的时间复杂度为（ ）。 A．O（n） B．O（n2） C．O（n3） D．O（1） 二、填空题（每空1分，共32分） 1．在线性结构、树形结构和图形结构中，直接前驱和直接后继结点之间分别存在着 、 和 的联系。 2．向一个循环队列中插入元素时，需要首先移动 ，然后再向所指位置 新插入的元素。 3．在一个循环队列Q中，判断队空的条件为 ，判断队满的条件为 。 4．在一棵二叉树中，假定度为2的结点有5个，度为1的结点有6个，则叶子结点数有 个。 5．对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为 个，其中 个用于指向子女结点， 个指针空闲着。 6．以折半查找方法查找一个线性表时，此线性表必须是 存储的 表。 7．表示图的三种存储结构为 、 和 。 8．在一个具有n个顶点的无向完全图中，包含有 条边，在一个具有n个顶点的有向完全图中，包含有 条边。 9．假定一组记录的排序码为（46，79，56，38，40，80），对其进行归并排序的过程中，第二趟归并后的结果为 。 10．快速排序在平均情况下的时间复杂度为 ，在最坏情况下的时间复杂度为 。 11．栈又称为 的表，队列又称为 的表。 12．数据的存储结构被分为 、 、 和 4种。 13．一个广义表中的元素分为 元素和 元素两类。 14．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为 和 。 15．假定一组记录的排序码为（46，79，56，38，40，84），则利用堆排序方法建立的初始堆为 。 三、运算题（每小题6分，共24分） 1．对于一个n×n的矩阵A的任意矩阵元素a[i][j]，按行存储时和按列存储时的地址之差是多少。（设两种存储时的开始存储地址均为LOC（0，0），每个元素所占存储单元数均为d） 2．已知一棵二叉数的中序和后序序列如下，求该二叉数的前序序列。 中序序列：c,b,d,e,a,g,i,h,j,f 后序序列：c,e,d,b,i,j,h,g,f,a 3.已知一个带权图的顶点集V和边集G分别为： V={0，1，2，3，4，5}； E={（0，1）19，（0，2）21，（0，3）14，（1，2）16，（1，5）5，（2，3）26，（2，4）11，（3，4）18，（4，5）6}； 试根据克鲁斯卡尔算法求出最小生成树，在下面填写依次得到的各条边。 ， ， ， ， 。 4．假定一组数据的初始堆为（84，79，56，42，40，46，50，38，20），请写出在堆排序阶段进行一次对换和筛运算后数据的排列情况。 四、阅读算法，回答问题（每小题8分，共16分） 1.int unknown(BinTreeNode*t) //指针t是二叉树的根指针 {if(t==NULL) return 0; else if(t(leftChild==NULL t(rightChild==NULL) return 1; else return unknown(t(leftChild)+ unknown(t(rightChild); } 该算法的功能为： 。 2.Void AB(list L) {InsertRear(L,30