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

《《数据结构》期末模拟试题二.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》期末模拟试题二一、单项选择题（每小题2分，共8分）1．当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。A．top++；B．top--；C．top=0；D．top；2．从一个顺序存储的循环队列中删除一个元素时，首先需要（）。A．队头指针加1B．队头指针减1C．取出队头指针所指的元素D．取出队尾指针所指的元素3．一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序（以位于最左位置的对象为基准）所得到的第一次划分结果

2、为（）。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、向所指位置新插入的元素。3．在一个循环队列Q中，判断队空的条件为，判断队满的条件为。4．在一棵二叉树中，假定度为2的结点有5个，度为1的结点有6个，则叶子结点数有个。5．对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为个，其中个用于指向子女结点，个指针空闲着。6．以折半查找方法查找一个线性表时，此线性表必须是存储的表。7．表示图的三种存储结构为、和。8．在一个具有n个顶点的无向完全图中，包含有条边，在一个具有n个顶点的有向完全图中，包含有条边。9．假定一组记录的排序码为（46，79，56，38，40，80），对其进

4、行归并排序的过程中，第二趟归并后的结果为。10．快速排序在平均情况下的时间复杂度为，在最坏情况下的时间复杂度为。11．栈又称为的表，队列又称为的表。12．数据的存储结构被分为、、和4种。13．一个广义表中的元素分为元素和元素两类。14．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为和。15．假定一组记录的排序码为（46，79，56，38，40，84），则利用堆排序方法建立的初始堆为。三、运算题（每小题6分，共24分）1．对于一个n×n的矩阵A的任意矩阵元素a[i][j]，按行存储时和按列存储时的地址

5、之差是多少。（设两种存储时的开始存储地址均为LOC（0，0），每个元素所占存储单元数均为d）2．已知一棵二叉数的中序和后序序列如下，求该二叉数的前序序列。中序序列：c,b,d,e,a,g,i,h,j,f后序序列：c,e,d,b,i,j,h,g,f,a3.已知一个带权图的顶点集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}；试根据克鲁斯卡尔算法求出最小生成树，在下面填写依次得

6、到的各条边。，，，，。4．假定一组数据的初始堆为（84，79，56，42，40，46，50，38，20），请写出在堆排序阶段进行一次对换和筛运算后数据的排列情况。四、阅读算法，回答问题（每小题8分，共16分）1.intunknown(BinTreeNode*t)//指针t是二叉树的根指针{if(t==NULL)return0;elseif(tàleftChild==NULL&&tàrightChild==NULL)return1;elsereturnunknown(tàleftChild)+unknown(tàright

7、Child);}该算法的功能为：。2.VoidAB(list&L){InsertRear(L,30);InsertFront(L,58);Delete(L,12);InsertRear(L,DeleteFront(L));}假定调用该算法时线性表L为（35，19，12，15），则调用返回后线性表L变为：。五、算法填空，在画有横线的地方填写合适的内容（10分）向以BST为树根指针的二叉搜索树上插入值为item的结点的递归算法。VoidInsert(BTreeNode*&BST,constElemType&item){if(

8、BST==NULL){BTreeNode*p=newBtreeNode;pàdata=item;;BST=p;}elseif(item