(数据结构)试题.doc

学习形式：脱产 . 夜大 . 函授 . 年级： 专业： 学号： 姓名： 线订装内数据结构试卷 第一部分 闭卷答题部分 答题时间为30分钟题目一二三四五六总分核分人题分3010108100得分得分评卷人一、单选题(每题2分，共30分)1研究数据结构就是研究（ ）A. 数据的逻辑结构 B. 数据存储结构C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其数据在运算上的实现2下面程序的时间复杂度为（ ） for(i=0;im;i+)for(j=0;jnext=NULL C. head-next=head D. head!=NULL5在循环双链表的p结点之后插入s结点的操作是（ ）A. p-rlink=s; s-llink=p;p-rlink-link=s;s-rlink=p-rlink;B. p-rlink=s;p-rlink-llink=s;s-llink=p;s-rlink=p-rlink;C. s-llink=p;s-rlink=p-rlink;p-rlink=s;p-rlink-llink=s;D. s-llink=p;s-rlink=p-rlink;p-rlink-llink=s;p-rlink=s;6一个具有M个单元的循环队列，其头尾指针分别尾front和rear，则当前队列中元素个数是（ ）。A. (rear-front+M) % M B. rear-front+1 C. rear-front-1 D. rear-front7判断循环队列为满(共MAX个单元，最多容纳MAX-1个元素)的条件（ ）A. front= = rear B. front != rear C. front= =(rear+1)%MAX D. front!=(rear+1)%MAX8设栈的输入序列是（1，2，3，4），则不可能是其出栈序列的是（ ）A. 1234 B. 2134 C. 1432 D. 4312 E. 32149串是一种特殊的线性表，其特殊性体现在（ ）A. 可以顺序存储 B. 数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字符10稀疏矩阵一般的压缩存储方法有两种，即（ ）A. 二维数组和三维数组 B. 三元组和散列C. 三元组和十字链表 D. 散列和十字链表11广义表运算式GetHead(GetTail(a,b,c),(x,y,z)是（ ）A. (a,b,c) B. a C. (x,y,z) D. x12按照二叉树的定义，具有3个结点的二叉树有（ ）种。A. 3 B. 4 C. 5 D. 613深度为5的二叉树上至多有（ ）个结点。A. 16 B. 32 C. 31 D. 1014二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则先序序列为（ ）A. EGFACDB B. EACBDGF C. EAGCFBD D. 上面都不对15在线索二叉树中，t所指结点没有左子树的充要条件是（）。A. t-lchild=NULL B. t-ltag=1 C. t-ltag=1& t-lchild=NULL D. 上面都不对得分评卷人二、填空题 （每空1分 ，共10分）1一个长度为n的线性表，采用顺序存储方式，若删除第i个元素时，需要向前移动 n-i 元素。2评价一个算法的好坏，主要从 正确性 ， 可读性 ， 健壮性 ， 效率和低存储量需求 几个方面。3线性表的两种存储结构分别为 顺序表 和 链表 。4设n阶下三角矩阵A已压缩至一维数组S0.(n*(n+1)/2)-1中，若按行主序，则Ai,j(0=i,j=j) 或j(j+1)/2+i (i=j) 或j(j+1)/2+i (inext;while(p) len+;p=p-next; return len; 6、编写一个算法，求一棵二叉树的深度（要求写出二叉树的定义）。typedef struct BTNode /*节点结构声明*/char data ; /*节点数据*/struct BTNode *lchild;struct BTNode *rchild ; /*指针*/*BiTree;int treedepth(BiTree t)/*计算二叉树的深度*/ int dep1=0,dep2=0; if(t=NULL) return 0;/*树空*/ else dep1=treedepth(t-lchild);/*计算结点左子树的深度*/ dep2=treedepth(t-rchild);