北师�?8考研�E�序设计与数据结构试题_跨考网

复习紧张�Q�焦头烂额？逆风轻袭�Q�来跨考秋季集训营�Q�帮你寻�Ҏ(gu��)���Q�定�Ҏ(gu��)���Q?/span> 了解一�?>

一、简�{�题�Q?0分）
　　1.数据�c�d��和抽象数据类型的含义
　　2.���法的特性与���法的时间复杂度
　　3.快速排序方法最好和最坏的情况是什么？���要分析说�?
　　4.栈、队列的共同点与不同点，说明其属于线形表的原�?
　　二、方法选择�Q?0分）
　　1.一���二叉排序树中各�l�点不相同，�Ʋ得��C��个由大到���的�l�点值递减序列�Q�你认�ؓ采用什么方法能得到要求的结果？
　　2.设有1000个无序元素，仅要求找出前10个最���元素，在下列排序方法中�Q�归�q�排序，基数排序�Q�快速排序，堆排序，插入排序�Q�，那种�Ҏ(gu��)��最好，��Z��么？
　　三、（40分，每题8分）
　　1.已知一个��@环单链表la�Q�av是可利用栈的头指针，��L���Q�个赋��D��句，完成���整个��@环链表释攄���功能。（卛_��表整个归�q�到可用的栈�I�间�Q?
　　2.�l�出求N阶hanoi塔的函数定义如下�Q�Hanoi �Q?int n�Q�char x�Q�char y �Q�char z �Q?
　　{ if �Q?n= =1�Q?move �Q?x �Q?�Q�z�Q?
　　Else{ hanoi�Q?n-1�Q?x�Q�z�Q�y�Q�；
　　Move�Q�x�Q�n�Q�z�Q�；
　　Hanoi�Q�n-1�Q�y�Q�x�Q�z�Q�；
　　}
　　}
　　写出执行hanoi�Q?�Q�a�Q�b�Q�c�Q�时递归函数的实在参变量变化�Q�以及move的搬�q�过�E��?
　　3.已知关键字序列�ؓ�Q�（75�Q?3�Q?2�Q?1�Q?2�Q?8�Q?6�Q?7�Q�，哈希表长�?0�Q�哈希函��Cؓ�Q�H�Q�K�Q�＝KMOD7�Q�解军_���H�用�U�性探���再散列法，要求构造哈希表�Q�求出等概率下查找成功查��N��度�?
　　4.已知一���二叉树�Q�中序序列DBCAFGE�Q�后序序列DCBGFEA�Q�构造该二叉树�?
　　5.�l�定权��|��(j��ng)8�Q?2�Q?�Q?�Q?6�Q?6�Q?｝，构造一个哈夫曼树，�q�计���其带权路径长度�?
　　四、编写程序（15分）
　　建立�U��Ş表，�Q�a1�Q�a2�Q�a3…。，an�Q�的单链表存储，�q�实现其���地逆置为（an�Q?�Q�an-1…a2.�Q�a1�Q��?
　　五、编写程序（10分）
　　在中序线索树中，要找出�׾l�点的前��q��点，请写出相兛_��数定义�?
　　Ltag Lc Data Rtag Rc
　　六、编写算法（20分）
　　已知有N个结点的无向图，采用��L��表结构存储，要求�Ҏ(gu��)��个连通子图中一个生成树中的各条辚w��层输出�Q�边的输出格式�ؓ�Q�ki�Q�kj�Q��?
　　七、编写算法（25分）
　　1.写出建立二叉树，二叉链表存储�l�构的算法。（10分）
　　2.已知二叉树采用二叉链表方式存放，要求对二叉树�?开始进行连�l�编��P��要求每个�l�点的编号大于其左右孩子的编��P��同一�l�点的左叛_��子中�Q�左孩子�~�号���于叛_��子编受���给出在二叉树中�l�点的数据域部分填写�Q�实现如上要求编��L��非递归���法。（10分）
　　3.已知二叉树采用二叉链表方式存放，�l�出判定它是否�ؓ一�?br>