2011安徽大学数据结构试卷

1、从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A、O(1) B、O(n) C、O(1Ogzn) D、O(n2)

2、向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A、O(n) B、O(1) C、O(n2) D、O(10g2n) 3、n个顶点的强连通图中至少含有( )。

4、A、n—l条有向边 B、n条有向边 C、n(n—1)／2条有向边 D、n(n一1)条有向边

4、在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A、HL＝ps p一>next＝HL B、p一>next＝HL；HL＝p3

C、 p一>next＝Hl；p＝HL； D、 p一>next＝HL一>next;HL一>next＝p

5、当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A、整形 B、引用型 C、指针型 D、常值引用型· 二、填空题

1、在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为 域和 域。

2、表示图的三种存储结构为 、 和 。

3、数据的存储结构被分为 、 、 和 四种。

4、在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定 该结点的值，右子树上所有结点的值一定 该结点的值。

5、对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为 ，对用邻接表表示的图进行任一种遍历时，其时间复杂度为 。 6、 中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为 。

7、假定一棵二叉树的结点数为18，则它的最小深度为 ，最大深度为 。

8、从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为 和 。 三、运算题。

1、已知一个带权图的顶点集V和边集G分别为： V＝{0，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}， 则求出该图的最小生成树的权。 最小生成树的权；

2、有7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点生成一棵哈夫曼树，求出该树的带权路径长度、高度、双分支结点数。 带权路径长度： 高度： 双分支结点数： 。 四、阅读算法，回答问题。 1、void AG(Queue&Q) { InitQueue(Q)；

inta[5]＝{6，12，5，15，8}；

for(int i＝0;i<5; i++)QInsert(Q，a[i])； QInsert(Q，QDelete(Q))； QInsert(Q，20)； QInsert(Q，QDelete(Q)十16)；

while(!QueueEmpty(Q))cout<InitList(L)； InsertRear(L;25)； InsertFront(L，50)； IntaL4]＝{5，8，12，15，36}; for(inti

＝0; i<5; i++)

if (a[i]％2＝＝0)InsertFront(L，a[i])； elselnsertRear(L，a[i])； } 该算法被调用执行后，得到的线性表L为：

一、单选题

1、C 2、A 3、B 4、B 5、B 二、填空题。

1、值(或data) 子表指针(或sublist) 2、邻接矩阵 邻接表 边集数组(次序无先后) 3、顺序结构、 链接结构 、索引结构 、散列结构 4、小于 大于(或大于等于) 5、O(n2) O(e) 6、5 18

7、3 x 2．4 56一*十 8、 1 3 三、运算题。 1、最小生成树的权：31 ／／ 2、带权路径长度：131 ／／ 高度：5 ／／ 双分支结点数：6 ／／ 四、阅读算法，回答问题。 1、（5， 15 ，8 ，6， 20 ，28） 2、(36，12，8，50，25，5，15)