新祥旭考研辅导-北京科技大学2001年数据结构考研试题.doc

《新祥旭考研辅导-北京科技大学2001年数据结构考研试题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京科技大学2001年试题(f)1.若将数据结构定义为一个二元组（D,R）,说明符号，D,R应分别表示什么？2.算法的时间复杂度和空间复杂度的含义是什么？3.设双向循环链表中结点的数据域，前驱和后继指针域分别为data,pre和next,试写出在指针p所指结点之前插入一s结点的c语言描述语句。4.设输入序列为a,b,c,d,是写出借助一个栈可得到的两个数输出序列和两各不能得到的输出序列。5.设c语言二维数组A[5][6]中每一个元素占6个存储单元，从首地址1000开始将其按行的顺序存储，A[3][5]的

2、地址LOC[3,5]=?6.若一刻完全二叉树中叶字结点的个数为N,且最底层结点数≧2，则此二叉树的深度H=？7.无向图的连同分量和有向图的强连通分量分别指什么？8.在一棵B+树上一般可进行那两种方式的查找运算?9.在构造HASH表中，通常有那几种处理冲突的方法？10.组织带检索文件的到排表优点是什么？二（10分）对单链表中中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。清填充算法中标出的空白处，完成其功能。Typedefstrucfnode{intdata;structnode*nex

3、t;}linknode,*link;VoidInsertsort(linkL){linkp,q,r,u;p=L->next;-----1----;while(-----2---){=L;q=L->next;while(-----3---&&q->data<=p->data){r=q;q=q->next;}u=p->next;-------4---;-------5---;p=u;}}三.(10分设循环队列Q[8]的当前状态如下：01234567Q:55 a1 a2a3a4a5  frontrear其中a

4、i(1=

5、、h的序号分别为1、2、3、4、5、6、7，请列出网G的邻接矩阵、画出网G的邻接表结构:2．2． 写出从顶点a出发,按“深度优先搜索”和“广度优先搜索”方法遍历网G所的到的顶点序列：3．3． 按Prim算法求出网G的一棵最小生成树。六．（18分）设记录的关键字（Key）集合K={11，2，13，22，5，16，6，27，1}1．1． 请依次取K中各值，构造一棵二叉排序树，并计算对此二叉树等概率查找情况下、查找成功的查找长度ASL；2．2． 设Hash表表长m=12，选取Hash函数的方法为“除留余数法”

6、，处理冲突的方法为“线性探测再散列”，请依次取K中各值，按所给条件构造出Hash表结构，并求对该表的平均查找长度ASL；3．3． 若选择的增量序列为（5，3，1），写出对K按“Shell排序”方法排序时，各趟排序结束时的结果（结果序列按升序排列），并将K调整成一个堆顶元素取最小值得堆。七.(20分此题统考生作)1．1． 1． 设Huffman树的根结点指针为ht,结点的权值、左子指针和右子指针域分别为Weight、Lchild和Rchild,试采用先序非递归遍历二叉树的方法，写出求Huffman树的带权

7、路径长度（WPL）的C语言描述算法：HWPL(ht):（注：算法中可调用栈操作的基本算法。）2．2． 2． 设无向图G已用邻接表结构储存，顶点表为GL[n](n为图中顶点数)，试用“广度优先搜索”方法，写出求图G中各连通分量的C语言描述算法：BFSCOM(GL)。（注：算法中可调用队列操作的基本算法。）八.(10分此题单考生作)设一棵二叉树如下：  A  BCFDE  GH  请将此二叉树转换成相应的森林，并写出对此森林安先序和中序遍历的结果序列。九.（20分此题单考生作）1．1． 1． 设表达式以字符

8、形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号（‘（’和‘）’）是否配对的C语言描述算法：EXYX(E);(注：算法中可调用栈操作的基本算法。)2．设文件f中记录的关键字（key）集合已存入数组k[n]中，请写出依次取k中各值、构造一棵二叉排序树bt的C语言描述算法：CBTREE(bt,k)。