2013年“数据结构与C程序设计”(代码991)试题一、单项选择题（本题共20分，每小题各2分）1．对于长度为n的线性表，建立其对应的单链表的时间复杂度为()
A．O(1)；B．O(log2n)；．O(n)；D．O(n2)
2．一般情况下，在一个双向链表中插入一个新的链结点，()
A．需要修改4个指针域内的指针；B．需要修改3个指针域内的指针；C．需要修改2个指针域内的指针；D．只需要修改1个指针域内的指针
3．假设用单个字母表示中缀表达式中的一个运算数(或称运算对象)，并利用堆栈产生中缀表达式对应的后缀表达式
对于中缀表达式A+B*(C/D-E)，当从左至右扫描到运算数E时，堆栈中的运算符依次是()
(注：不包含表达式的分界符)A．+*/-；B．+*(/-；C．+*-；．+*(-
4．若某二叉排序树的前序遍历序列为50,20,40,30,80,60,70，则后序遍历序列为()
A．30,40,20,50,70,60,80；B．30,40,20,70,60,80,50；C．70,60,80,50,30,40,20；D．70,60,80,30,40,20,50
5．分别以6,3,8,12,5,7对应叶结点的权值构造的哈夫曼(Huffman)树的深度为()
A．6；B．5；C．4；D．3
6．下列关于图的叙述中，错误的是()
A．根据图的定义，图中至少有一个顶点；B．根据图的定义，图中至少有一个顶点和一条边(弧)；C．具有n个顶点的无向图最多有n(n-1)/2条边；D．具有n个顶点的有向图最多有n(n-1)条边(弧)
7．若在有向图G的拓扑序列中，顶点vi在顶点vj之前，则下列4种情形中不可能出现的是()
A．G中有弧；B．G中没有弧；C．G中有一条从顶点vi到顶点vj的路径；D．G中有一条从顶点vj到顶点vi的路径
8．下列关于查找操作的叙述中
