20082009算法与数据结构试卷B

《20082009算法与数据结构试卷B》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、北京物资学院2008—2009学年第1学期期末考试学号：班级：姓名：装订线内不要答题算法与数据结构（Ｃ）课程试卷（B卷）题号一二三四五六七八九总分评分评卷人审核人：一、名词解释（8分，每小题2分）1、数据结构的逻辑结构2、栈3、小根堆4、图的邻接矩阵二、（16分）填空1、抽象数据类型由一种数据结构和在其上的所组成。2、算法时间复杂度可以用与样本量有关的表示，简称大O表示法。3、顺序存储的线性表是由作为存储空间的，其最大存储空间定义变量为。4、队列插入元素的操作是在进行，删除操作是在进行。5、如果某种数

2、据结构的存储类型定义如下：typedefintDataType;structNode;typedefstructNode*PNode;structNode{DataTypeinfo;PNodelink;};typedefstructNode*LinkList;则此数据类型定义为：，其中link的含义是。6、在递归函数调用时，计算机自动建立栈，栈中至少包含二个域：和参数域。7、一棵度为3的树，它的结点个数是12，则它的最小高度是；最大高度是。8、对一棵二叉排序树进行中序遍历，得到的结点序列一定是。9、一

3、个图的边集为{<0,2>,<0,4>,<2,5><3,2>,<4,1><4,3>}，从0顶点出发进行深度遍历的结果是：；从0顶点出发进行广度遍历的结果是：。10、若根据数据集合{24，44，36，48，52，72，62，58}建立散列表，采用h(K)=K%13计算散列地址，并采用链接法处理冲突，则元素72的初始散列地址为：，数据集合中的有地址冲突。三、选择题（10分）1、在栈的有关定义中以下哪种说法是正确的：（）A．栈顶元素只有出栈后才能读。B．栈是一种链接的线性表。C.栈是一种后进先出的线性表。D.

4、栈是一种先进先出的线性表。2、若顺序循环队列有MAXNUM个存储单元，front、rear分别为队首和队尾指针，队首和队尾的数据类型为（）A．intB.charC.floutD.struct3、对于链接存储的队列，front、rear分别为队首和队尾指针，队首和队尾的数据类型为（）A．intB.charC.floutD.指针类型4、在广义表结点定义中，每个结点由三个域组成：atominfolink其中atom是一个标志位，atom＝0时表示本结点为广义表，此时info存放子广义表中（）。A．第一个元素

5、结点的元素值B.第一个元素结点的地址C.下一个元素结点的元素值D.下一个元素结点的地址5、一棵二叉树如下，此二叉树中根周游结果为（）。BCFEDA．ABCDEFB．DBAFECC．DBACEFD．ADBFEC6、对一个有n个结点的二叉树来说，如果将其扩充，其扩充二叉树中有（）个外部结点。A．n－1B．nC．n＋1D．2n7、由权值分别为2、3、4、6、7、9的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。A.39B.49C.59D.698、已知一个有向图的边集为{<0,1>6,<0,2>5,<0,

6、3>2,<1,4>10,<3,2>2,<2,4>9,<3,4>8}，则该图从0顶点到其余各顶点的最短路径是（）。A.V0－>V1V0－>V1－>V2V0－>V1－>V2－>V3V0－>V1－>V2－>V3－>V4B.V0－>V3V0－>V3－>V1V0－>V3－>V1－>V2V0－>V3－>V1－>V2－>V4C.V0－>V3V0－>V3－>V2V0－>V3－>V2－>V1V0－>V3－>V2－>V1－>V4D.V0－>V3V0－>V3－>V2V0－>V1V0－>V3－>V2－>V49、利用二叉排序树

7、进行检索，算法的时间复杂度是（）。A．O(1)B．O(log2n)C．O(n)D．O(n2)10、下图是个完全二叉树，树中元素存于A[]中，若将其建成大根堆，以下哪个A[]是堆元素的A[]（）。A．A[]={97,87,12,56,54,36,46,34}B．A[]={97,87,56,46,54,36,34,12}C．A[]={97,87,56,54,46,36,34,12}D．A[]={12,34,36,46,54,56,87,97}5434125687364697四、（12分）以下有一组算法，请

8、根据各算法的不同，回答不同的问题。算法1：//顺序表结构定义和在表尾插入元素的算法structSeqList{intMAXNUM;intn;DataType*element;};typedefstructSeqList*PSeqList;intInsertRear(PSeqListpalist,DataTypex){if(palist->n==palist->MAXNUM){printf("Listoverflow!");return0;}palis