下载文档原格式
上海交通大学99年研究生考试数据结构及程序设计技术试题上海交通大学一九九九年硕士生入学考试试题试题序号：19（答案清写在答题纸上）试题名称：数据结构及程序设计技术说明：试卷共十题。
第I－5题只需写出实现算法的函数或过程即可。
不必写出整个程序，只准使用Pascal或C编写（类Pascal和类C也可），必须写清楚算法设计思想及所用的数据结构，对程序要加以适当的注解，程序应有良好的结构，不得使用GOTO语句。
第6－10题直接写出答案即可。
1．假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将表A和表B归并成一个按元素值非递减有序（允许值相同）排列的线性表C，并要求利用原表（即表A和表B）的结点空间存放表C。
（12’）2．利用两个栈S1和S2模拟一个队列，写出入队和出队的算法（可用栈的基本操作）。
（12’）3．试以二叉链表作存储结构，编写按层次顺序遍历二叉树的算法。
（12’）4．已知一棵二叉树的先序遍历序列和中序遍历序列分别存于两个一维数组中；试编写算法建立该二叉树的二叉链表。
（12’）5．写出从哈希表中删除关键字为K的一个记录的算法。
设哈希函数为h，解决冲突的方法为链地址法。
（12’）6.考虑下图：（12’）1）从顶点A出发，求它的深度优先生成树。
2）从顶点E出发，求它的广度优先生成树。
3）根据普里姆（Prim）算法，求它的最小生成树。
7．试求按关键字序列（12，1，4，3，7，8，1O，2）插入生成的二叉排序树和平衡二叉树。
（7’）8．给出一组关键字T=（12，2，16，3O，8，28，4，10，ZO，6，18）。
写出用下列算法从小到大排序时第一趟结束时的序列：（9’）1）希尔排序（第一趟排序的增量为5）2）快速排序(选第一个记录为枢轴(分隔))3）链式基数排序（基数为1O）9．判别序列（12，70，33，65，24，56，48，92，86，33）是否为堆，如果不是，则把它调整为堆，试给出堆排序方法在平均时间性能、最坏情况下的时间性能和辅助存储量，并与快速排序方法在以上三方面进行比较。
专业课复习资料（最新版）封面数据结构与C语言程序设计一. 是非题（2’⨯10）（ ）1、 队列逻辑上是一个表头和表尾既能插入又能删除的线性表。
（ ）2、 任何一个递归过程都可以转换成非递归过程。
（ ）3、 与n个键值的集合{k1,k2,…,kn}相对应的堆是唯一的。
（ ）4、 在索引顺序表上实现分块查找，在等概率查找情况下，其查找长度只与表中元素个数有关，而与每块中元素个数无关。
（ ）5、 所谓加权无向图G的最小生成树T就是将G中各结点间的最短路径作为边所构造出来的G的子图。
（ ）6、 在10万个随机排列的数据中，要选出5个最小的数，采用快速排序比采用Shell排序、堆排序及各种直接排序法都快。
（ ）7、 B树查找算法的时间复杂性为O（n）。
（ ）8、 哈希表查找无需进行关键字的比较。
（ ）9、 在执行某个排序过程中，出现排序码朝着最终位置相反方向移动，则该算法是不稳定的。
（ ）10、任何有向图的顶点都可以按拓扑序排序。
二.填空题（2’⨯6）1．假设用于通信的电文由8个字母组成，其频率分别为0.07，0.19,0.02,0.06,0.32,0.03,0.21,0.10, 为这8个字母设计哈夫曼编码，其中编码长度最大的字母的编码是 位。
2．已知二叉树按中序遍历所得到的结点序列为DCBGEAHFIJK， 按后序遍历所得到的结点序列为DCEGBFHKJIA， 按先序遍历所得到的结点序列为 。
3. 设哈希表长度为11，散列函数H(k)=k MOD 11, 若输入顺序为（18,10,21,9,6,3,16,25,7）,处理冲突方法为线性探测再散列，请构造哈希表 。
果 。
5．已知模式匹配的KMP算法中模式串t=’adabbadada’，其next函数的值为 。
6．在置换-选择排序中，假设工作区的容量为w，若不计输入、输出的时间，则对n个记录的文件而言，生成所有初始归并段所需时间为 。
三.简答题（6’⨯5）1．有n个不同的英文单词，它们的长度相等，均为m，若n>>50，m<5，试问采用什么排序方法时间复杂度最佳？为什么？2．对于一个栈，给出输入序列A，B，C，试给出全部可能的输出序列。
2022年上海交通大学软件工程专业《数据库原理》科目期末试卷B（有答案）一、填空题1、数据管理技术经历了______________、______________和______________3个阶段。
2、有两种基本类型的锁，它们是______和______。
3、数据仓库主要是供决策分析用的______，所涉及的数据操作主要是______，一般情况下不进行。
4、数据库系统是利用存储在外存上其他地方的______来重建被破坏的数据库。
方法主要有两种：______和______。
5、在SQL Server 2000中，某数据库用户User在此数据库中具有对T 表数据的查询和更改权限。
现要收回User对T表的数据更改权，下述是实现该功能的语句，请补全语句。
_____UPDATE ON T FROM User；6、完整性约束条件作用的对象有属性、______和______三种。
7、在SQL语言中，为了数据库的安全性，设置了对数据的存取进行控制的语句，对用户授权使用____________语句，收回所授的权限使用____________语句。
8、关系系统的查询优化既是关系数据库管理系统实现的关键技术，又是关系系统的优点。
因为，用户只要提出______，不必指出 ______。
9、某事务从账户A转出资金并向账户B转入资金，此操作要么全做，要么全不做，为了保证该操作的完整，需要利用到事务性质中的_____性。
10、以子模式为框架的数据库是______________；以模式为框架的数据库是______________；以物理模式为框架的数据库是______________。
二、判断题11、关系是一张二维表。
（）12、在关系模式中，主码和候选码可以有多个。
（）13、SQLServer有两种安全性认证模式：WindowsNT和SQLServer。
（）14、在CREATEINDEX语句中，使CLUSTERED来建立簇索引。
一、选择题1. 算法的计算量的大小称为计算的〔B〕。
【邮电大学2000 二、3 〔20/8分〕】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于〔C 〕【中科院计算所1998 二、1 〔2分〕】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是〔C〕，它必须具备〔B〕这三个特性。
(1) A．计算方法 B. 排序方法C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩大性B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、平安性【理工大学1999 一、1〔2分〕【交通科技大学1996 一、1〔4分〕】4．一个算法应该是〔B〕。
【大学1998 二、1〔2分〕】A．程序B．问题求解步骤的描述C．要满足五个根本特性D．A和C.5. 下面关于算法说法错误的选项是〔D〕【理工大学2000 一、1〔1.5分〕】A．算法最终必须由计算机程序实现B.为解决*问题的算法同为该问题编写的程序含义是一样的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的选项是〔C〕【理工大学2000 一、2 〔1.5分〕】(1〕算法原地工作的含义是指不需要任何额外的辅助空间〔2〕在一样的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法〔3〕所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界〔4〕同一个算法，实现语言的级别越高，执行效率就越低4A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据构造分为〔C〕两大类。
【交通科技大学1996 一、4〔2分〕】A．动态构造、静态构造B．顺序构造、链式构造C．线性构造、非线性构造D．初等构造、构造型构造8．以下与数据的存储构造无关的术语是〔D〕。
【北方交通大学2000 二、1〔2分〕】A．循环队列 B. 链表 C. 哈希表 D.栈9．以下数据构造中，哪一个是线性构造〔D〕.【北方交通大学2001 一、1〔2分〕】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储构造无关.〔A〕【北方交通大学2001 一、2〔2分〕】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对*的赋值语句的频度为〔C〕【工商大学2001 一、10〔3分〕】FOR i:=1 TO n DOFOR j:=1 TO n DO*:=*+1;A．O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是〔D〕A. O〔n〕B. O(nlogn)C. O(n3)D. O(n2)【理工大学1998一、1(2分)】13．以下哪个数据构造不是多型数据类型〔D〕【大学1999 一、3〔1分〕】A．栈B．广义表C．有向图D．字符串14．以下数据构造中，〔A〕是非线性数据构造【大学1999 一、4】A．树B．字符串C．队D．栈15. 以下数据中，〔C〕是非线性数据构造。
2007年上海交通大学计算机研究生机试真题1036: Old Bill题目描述Among grandfather's papers a bill was found. 72 turkeys $_679_The first and the last digits of the number that obviously represented the total price of those turkeys are replaced here by blanks (denoted _), for they are faded and are illegible. What are the two faded digits and what was the price of one turkey?We want to write a program that solves a general version of the above problem.N turkeys $_XYZ_The total number of turkeys, N, is between 1 and 99, including both. The total price originally consisted of five digits, but we can see only the three digits in the middle. We assume that the first digit is nonzero, that the price of one turkeys is an integer number of dollars, and that all the turkeys cost the same price.Given N, X, Y, and Z, write a program that guesses the two faded digits and the original price. In case that there is more than one candidate for the original price, the output should be the most expensive one. That is, the program is to report the two faded digits and the maximum price per turkey for the turkeys.输入The first line of the input file contains an integer N (0<N<100), which represents the number of turkeys. In the following line, there are the three decimal digits X, Y, and Z., separated by a space, of the original price $_XYZ_.输出For each case, output the two faded digits and the maximum price per turkey for the turkeys.样例输入726 7 952 3 7780 0 5样例输出3 2 5119 5 184752007年上海交通大学计算机研究生机试真题1037: Powerful Calculator题目描述Today, facing the rapid development of business, SJTU recognizes that more powerful calculator should be studied, developed and appeared in future market shortly. SJTU now invites you attending such amazing research and development work. In most business applications, the top three useful calculation operators are Addition (+), Subtraction (-) and Multiplication (×) between two given integers. Normally, you may think it is just a piece of cake. However, since some integers for calculation in business application may be very big, such as the GDP of the whole world, the calculator becomes harder to develop. For example, if we have two integers 20 000 000 000 000 000 and 4 000 000 000 000 000, the exact results of addition, subtraction and multiplication are: 20000000000000000 + 4000000000000000 = 24 000 000 000 000 000 20000000000000000 - 4000000000000000 = 16 000 000 000 000 00020000000000000000 × 4000000000000000 = 80 000 000 000 000 000 000 000 000 000 000Note: SJTU prefers the exact format of the results rather than the float format or scientific remark format. For instance, we need "24000000000000000" rather than 2.4×10^16.As a programmer in SJTU, your current task is to develop a program to obtain the exact results of the addition (a + b), subtraction (a - b) and multiplication (a × b) between two given integers a and b.输入 Each case consists of two separate lines where the first line gives the integer a and the second gives b (|a| <10^400 and |b| < 10^400).输出For each case, output three separate lines showing the exact results of addition (a + b), subtraction (a - b) and multiplication (a × b) of that case, one result per lines. 样例输入200000000000000004000000000000000样例输出24000000000000000160000000000000002007年上海交通大学计算机研究生机试真题1038: Sum of Factorials题目描述John von Neumann, b. Dec. 28, 1903, d. Feb. 8, 1957, was a Hungarian-American mathematician who made important contributions to the foundations of mathematics, logic, quantum physics, meteorology, science, computers, and game theory. He was noted for a phenomenal memory and the speed with which he absorbed ideas and solved problems. In 1925 he received a B.S. diploma in chemical engineering from Zurich Institute and in 1926 a Ph.D. in mathematics from the University of Budapest, His Ph.D. dissertation on set theory was an important contributions to the subject.At the age of 20, von Neumann proposed a new definition of ordinal numbers that was universally adopted. While still in his twenties, he made many contributions in both pure and applied mathematics that established him as a mathematician of unusual depth. His Mathematical Foundation of Quantum Mechanics (1932) built a solid framework for the new scientific discipline.During this time he also proved the mini-max theorem of GAME THEORY. He gradually expanded his work in game theory, and with coauthor Oskar Morgenstern he wrote Theory of Games and Economic Behavior (1944).There are some numbers which can be expressed by the sum of factorials. For example 9, 9 = 1! + 2! + 3! . Dr. von Neumann was very interested in such numbers. So, he gives you a number n, and wants you to tell whether or not the number can be expressed by the sum of some factorials.Well, it is just a piece of case. For a given n, you will check if there are some xi, and let n equal to Σt (上标) i=1（下标）xi! (t≥1, xi≥0, xi = xj <==> i = j)t即Σxi! (t≥1, xi≥0, xi = xj <==> i = j)i=1If the answer is yes, say "YES"; otherwise, print out "NO".输入You will get a non-negative integer n (n≤1,000,000) from input file.输出For the n in the input file, you should print exactly one word ("YES" or "NO") in a single line. No extra spaces are allowed. 样例输入92样例输出YESYES2007年上海交通大学计算机研究生机试真题1039: Zero-complexity Transposition题目描述You are given a sequence of integer numbers. Zero-complexity transposition of the sequence is the reverse of this sequence. Your task is to write a program that prints zero-complexity transposition of the given sequence.输入For each case, the first line of the input file contains one integer n-length of the sequence (0 ＜n ≤ 10 000). The second line contains n integers numbers-a1, a2, …, an (-1 000 000 000 000 000 ≤ ai ≤ 1 000 000 000 000 000).输出For each case, on the first line of the output file print the sequence in the reverse order.样例输入5-3 4 6 -8 9样例输出9 -8 6 4 -3时间限制: 1 Sec 内存限制: 32 MB提交: 136 解决: 57题目描述Output the k-th prime number.输入k≤10000输出The k-th prime number.样例输入37样例输出5172008年上海交通大学计算机研究生机试真题1041: Simple Sorting时间限制: 1 Sec 内存限制: 32 MB提交: 380 解决: 140题目描述You are given an unsorted array of integer numbers. Your task is to sort this array and kill possible duplicated elements occurring in it.输入For each case, the first line of the input contains an integer number N representing the quantity of numbers in this array(1≤N≤1000). Next N lines contain N integer numbers(one number per each line) of the original array.输出For each case ,outtput file should contain at most N numbers sorted in ascending order. Every number in the output file should occur only once.样例输入68 8 7 3 7 7样例输出3 7 82008年上海交通大学计算机研究生机试真题1042: Coincidence时间限制: 1 Sec 内存限制: 32 MB提交: 57 解决: 25题目描述Find a longest common subsequence of two strings.输入First and second line of an input contain two strings of lowercase character a…z. There are no spaces before, inside or after the strings. Lengths of strings do not exceed 100.输出In the first line of output file k – the length of a longest common subsequence.样例输入abcdcxbydz样例输出2题目描述We now use the Gregorian style of dating in Russia. The leap years are years with number divisible by 4 but not divisible by 100, or divisible by 400.For example, years 2004, 2180 and 2400 are leap. Years 2004, 2181 and 2300 are not leap.Your task is to write a program which will compute the day of week corresponding to a given date in the nearest past or in the future using today’s agreement about dating.输入There is one single line contains the day number d, month n ame M and year number y(1000≤y≤3000). The month name is the corresponding English name starting from the capital letter.输出Output a single line with the English name of the day of week corresponding to the date, starting from the capital letter. All other letters must be in lower case.样例输入9 October 200114 October 2001样例输出TuesdaySunday提示Month and Week name in Input/Output: January, February, March, April, May, June, July, August, September, October, November, DecemberSunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday2008年上海交通大学计算机研究生机试真题1044: Pre-Post题目描述We are all familiar with pre-order, in-order and post-order traversals of binary trees. A common problem in data structure classes is to find the pre-order traversal of a binary tree when given the in-order and post-order traversals. Alternatively, you can find the post-order traversal when given the in-order and pre-order. However, in general you cannot determine the in-order traversal of a tree when given its pre-order and post-order traversals. Consider the four binary three below:All of these trees have the same pre-order and post-order traversals. This phenomenon is not restricted to binary tree, but holds for general m-ary trees as well.输入For each case, there is only one line of the form m indicating that the trees are m-ary trees, is the pre-order traversal and is the post-order traversal. All traversal strings will consist of lowercase alphabetic characters. For all input instances, 1≤m≤20 and the length of and will be between 1 and 26 inclusive. If the length of is k(which is the same as the length of , o f course), the first k letters of the alphabet will be used as pre-order traversal string, the other k letters as post-order traversal string.输出For each case, you should output one line containing the number of possible trees which would result in the pre-order and post-order traversals for the instances. Output value will be within the range of a 32-bit unsigned integer. You are guaranteed that there is at least one tree with the given pre-order and post-order traversals.样例输入2 abc cba2 abc bca10 abc bca13 abejkcfghid jkebfghicda样例输出414512翻一下是21,34翻一下是43,12+34是46,46翻一下是64，现在又任意两个正整数，问他们两个数反转的和是否等于两个数的和的反转。
模拟题一、有一只猫抓了n (n>1)个老鼠后向老鼠宣布：老鼠按自然数进行编号（1～n），并按自然数顺序排队，以后先后次序不准变；于是猫每天吃掉编号为奇数的老鼠，剩下的老鼠再按原次序进行自然数编号，直至某一天只剩下一只小老鼠；而该小老鼠是猫从第一天起就想吃掉的那只，请问这只小老鼠的最初编号是几？（１）用链结构实现，链的每个节点所包含的“数据域”信息是老鼠的最初编号（从１开始编号），另一个信息是链的下一节点地址。
（２）建立一条有n个节点的链：先创建一个空链，然后向链尾插入n 个节点。
（３）开始删除奇数节点：从链首开始删除“奇”节点，直至链尾；判断链是否只剩下一个节点？不是则循环执行上一步，是则结束循环。
（４）输出结果。
（５）程序编写完成后，请以f1.c或f1.cpp作为文件名存放到F盘上。
答案：#include <iostream.h>#include <assert.h>struct mouse //链“节点”类声明{int n;mouse *nextptr;};int cat_mouse(int num) //函数定义{mouse *headptr=0,*tailptr=0,*frontptr,*p;int i;//先把1个老鼠加入链作为链首节点headptr=tailptr=new mouse;assert(headptr!=NULL); //动态内存分配异常处理headptr->n=1; //老鼠的编号headptr->nextptr=NULL;//在链尾再添加n-1个老鼠for(i=2;i<=num;++i){p=new mouse;assert(p!=NULL);p->n=i;cout<<p->n<<" ";tailptr->nextptr=p;tailptr=p;tailptr->nextptr=NULL; //设置链尾节点的“下一节点地址”为空//开始删除老鼠while(headptr!=tailptr) //每循环一次，删除链上的奇节点，直至只剩下１个节点 { p=headptr->nextptr; //链的首节点总是先被删除delete headptr; //析构首节点headptr=frontptr=p; //本次循环的第２个节点成为链的首节点 i=２; //从第２个节点开始循环：删除链的奇节点 while(p!=NULL) //从２开始循环至链尾节点{if((i%2)==１) //是奇节点{if (p->nextptr==NULL) //如果该奇节点是最后一个节点 {frontptr->nextptr=NULL; //前一节点成为链的尾节点tailptr=frontptr;delete p;p=NULL; //因本循环的判断条件是p!=NULL,到链尾，所以置为０ }else //是奇节点但不是尾节点，删除{frontptr->nextptr=p->nextptr; //从链上删除该奇节点 delete p;p=frontptr->nextptr; //下一节点的地址已保存在frontPtr的 nextPtr中 ++i;} //frontPtr成为被删节点的下一节点的上一节点，故值不变 }else //不是奇节点，不删除{frontptr=p;p=p->nextptr;++i;}}}return headptr->n; //返回最后一个节点的编号}void main() //主函数{int i, num;do{cout<<"\n请输入老鼠的只数（大于1，输入0退出）：";cin>>num;if(num>1){i=cat_mouse(num);cout<<"最后剩下的一只老鼠是："<<i<<endl;}}while(num!=0);以下为软件运行环境实效（在C++6.0中书写好的答案截图）注意点：1、考试考号和座位号（上机号）有一定的对应关系，跟老师确认后输入，以免做了成绩给了别人；2、就一大题，6.00开考，7.00结束；3、后面的截图是软件的实际操作界面，作为参考；。
本文档由标准美女（标准王国）整理，仅作学习交流使用。
如文档存在缺页、字迹模糊、乱码等情况，请大家通过论坛消息与我联系。
上海交通大学一九九七年硕士研究生入学考试试题试题名称：数据结构及程序设计技术试题编号：１９题一（６分）有五个数依次进栈：1,2,3,4,5.在各种出栈的序列中，以3,4先出的序列有哪几个。
（３在４之前出栈）题二（４分）试写出进栈操作，出栈操作算法的时间复杂性。
题三（４分）已知ＫＭＰ串匹配算法的模式串是AABBAAB,试写出改进后的NEXT信息帧。
题四（４分）设某通信电文由Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ六个字符组成，它们在电文中出现的次数分别是16,5,9,3,20,1。
试画出编码用的哈夫曼树。
题五（５分）已知某排序平衡二叉树Ｔ具有下列特点：（１）结点的关键字均在1到9范围内；（２）在Ｔ中存在一个关键字为n1的叶结点，若删去该结点，立即插入一个关键字为n1的结点，得到的平衡树与原Ｔ不相同；（３）在Ｔ中存在另一个关键字为n2的非叶结点，删去它，并立即插入n2结点，得到与原Ｔ相同的平衡树；（４）在Ｔ中插入某n3结点后立即删除它，得到的平衡树与原Ｔ不相同。
试画出具有上述特点的最简单（结点个数最少）的平衡树Ｔ，并写明n1,n2,n3分别等于几？题六（９分）某整型数组Ａ的１０个元素值依次为6,2,9,7,3,8,4,5,0,1,用下列各排序方法，将Ａ中元素由小到大排序。
（1）取第一个元素值６作为分割数，（2）试写出快速排序第一次分隔后Ａ中的结果。
（3）用堆排序，（4）试写出将第一个选出的数据放在Ａ的最后位置上，（5）将Ａ调整成堆后的Ａ中结果。
（6）用基数为３的基数排序法，（7）试写出第一次分配和收集后Ａ中的结果。
题七（１４分）某赋权有向图及它的单邻接表如下：（1）试写出深度优先搜索顺序。
（2）画出深度优先生成树。
（3）将该图作为ＡＯＥ网络图，（4）试写出Ｃ的最早发生时间及活动ＦＣ的最晚开始时间。
（5）用Dijkstra算法计算源点Ａ到各顶点的最短路径，（6）试写出当计算出ＡＤ及ＡＧ的最短路径时，（7）Ａ到其它各点路径（中间结点）的值。
填空1.在顺序表中插入或者删除一个元素，需要平均移动一半元素，具体移动的元素个数与插入位置有关。
2.向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素是，需要向后移动n-i+1个元素3.向一个长度为n的向量中，删除第i个元素(1≤i≤n+1)时，需要向前移动n-i个元素4.在顺序表访问任意节点的时间复杂度为O(1)5.顺序表中逻辑上相邻元素的物理位置一定相邻，单链表中逻辑上相邻的元素的物理位置不一定相邻6.在单链表中，除了首节点外，任一节点的存储位置由前驱节点指示7.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构8.设单链表的节点结构为(data,next),next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y插入结点x之后，则需要执行以下语句：py->next=px->next,px->next=py9.连式存储的提点时利用了指针来表示数据元素之间的逻辑关系10.对于双向链表，在两个结点之间插入一个新节点需要修改的指针共4个，单链表为2个11.循环单链表的最大优点是：可以从任一节点查找数据12.已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：p->next=p->next->next,free(p->next)13.带头结点的双向循环链表L中只有一个元素结点的条件是：L->next->next==L14.在单链表L中，指针p所指结点有后继结点的条件是：p->next!=null15.带头结点的双循环链表L为空表的条件是：L->next==L&&L->front==L判断16.链表中的头结点仅起到标识的作用。
（F）17.顺序存储结构的主要缺点是不利于插入或者删除操作。
程序设计试题样题及参考答案一．选择题1. 若用数组名作为函数调用的实参，传递给形参的是A。
A．数组的第一个元素的地址。
B．数组第一个元素的值。
C．数组全部元素的地址。
D．数组全部元素的值。
2. 在C程序中，main() 的位置C。
A. 必须作为第一个函数。
B.必须作为最后一个函数。
C.可以任意。
D.必须放在它调用的函数之后。
3、下列程序中，编译不会出错的语句是 A 。
#include <iostream.h>class Base{public:Base(){}Base(int i) { data = i; }private:int data;};class Derived: public Base{public:Derived():Base(0) {}Derived(int x):Base(x){}};int main(){Derived d1(1);Base *pb,b1;pb = &d1; //Ad1 = b1; //BBase &refB = d1;Derived d2 = *pb; //CDerived &refD = refB; //Dreturn 0;}答案：A注释：公有继承时，派生类是基类的子类型，反之则不成立。
具有子类型关系的基类和派生类的对象之间满足如下赋值兼容规则： 派生类对象的地址可以赋值给指向基类的指针；♦派生类的对象可以初始化基类的引用；派生类的对象可以赋值给基类的对象，即用派生类对象中从基类继承来的成员，逐个赋值给基类对象的成员。
4、判断fun,Y3::fun,Z2::fun中的各条语句是正确/错误。
class X{public:int a;};class Y1 : public X{ };class Y2 : protected X{ };class Y3 : private X{private:void fun(Y1 *py1,Y2 *py2,Y3 *py3);};class Z2 : public Y2{private:void fun(Y1 *py1,Y2 *py2,Y3 *py3);};void fun(Y1 *py1,Y2 *py2,Y3 *py3){py1->a = 7; //①py2->a = 7; //②py3->a = 7; //③}void Y3::fun(Y1 *py1,Y2 *py2,Y3 *py3){py1->a = 7; //④py2->a = 7; //⑤py3->a = 7; //⑥}void Z2::fun(Y1 *py1,Y2 *py2,Y3 *py3){ py1->a = 7; //⑦py2->a = 7; //⑧py3->a = 7; //⑨}答案：①正确②错误③错误④正确⑤错误⑥正确⑦正确⑧错误⑨错误注释：♦派生类Y1从基类X公有继承，基类成员a在Y1中仍然是公有成员，所以Y1类型的指针py1可以可以访问a成员，因此①④⑦正确。
二零零七年上海交通大学计算机上机复试真题Problem A. Old BillInput file: standard inputOutput file: standard outputAmong grandfather's papers a bill was found.72 turkeys $_679_The first and the last digits of the number that obviously represented the total price of those turkeys are replaced here by blanks (denoted _), for they are faded and are illegible. What are the two faded digits and what was the price of one turkey?We want to write a program that solves a general version of the above problem.N turkeys $_XYZ_The total number of turkeys, N, is between 1 and 99, including both. The total price originally consisted of five digits, but we can see only thethree digits in the middle. We assume that the first digit is nonzero, that the price of one turkeys is an integer number of dollars, and that all the turkeys cost the same price.Given N, X, Y, and Z, write a program that guesses the two faded digits and the original price. In case that there is more than one candidate for the original price, the output should be the most expensive one. That is, the program is to report the two faded digits and the maximum price per turkey for the turkeys.InputThe first line of the input file contains an integer N (0<N<100), which represents the number of turkeys. In the following line, there are thethree decimal digits X, Y, and Z., separated by a space, of the original price $_XYZ_.OutputFor the input case, there may be more than one candidate for the original price or there is none. In the latter case your program is to report 0. Otherwise, if there is more than one candidate for the original price, the program is to report the two faded digits and the maximum price per turkey for the turkeys.Sample input and outputStandard input standard output72 3 2 5116 7 95 9 5 184752 3 778 00 0 5Problem B. Powerful CalculatorInput file: standard inputOutput file: standard outputToday, facing the rapid development of business, SJTU recognizes that more powerful calculator should be studied, developed and appeared in futuremarket shortly. SJTU now invites you attending such amazing research and development work.In most business applications, the top three useful calculation operatorsare Addition (+), Subtraction (-) and Multiplication (×) between two given integers. Normally, you may think it is just a piece of cake. However,since some integers for calculation in business application may be verybig, such as the GDP of the whole world, the calculator becomes harder to develop.For example, if we have two integers 20 000 000 000 000 000 and 4 000 000000 000 000, the exact results of addition, subtraction and multiplicationare:20000000000000000 + 4000000000000000 = 24 000 000 000 000 000 20000000000000000 - 4000000000000000 = 16 000 000 000 000 000 20000000000000000 × 4000000000000000 = 80 000 000 000 000 000 000 000 000 000 000Note: SJTU prefers the exact format of the results rather than the floatformat or scientific remark format. For instance, we need "24000000000000000" rather than 2.4×10^16.As a programmer in SJTU, your current task is to develop a program toobtain the exact results of the addition (a + b), subtraction (a - b) and multiplication (a × b) between two given integers a and b.InputThe input file consist of two separate lines where the first line gives theinteger a and the second gives b (|a| <10^200 and |b| < 10^200).OutputFor the input file, output three separate lines showing the exact resultsof addition (a + b), subtraction (a - b) and multiplication (a × b) ofthat case, one result per lines.Sample input and outputStandard input standard output 20000000000000000 24000000000000000 4000000000000000 1600000000000000080000000000000000000000000000000Problem C. Sum of FactorialsInput file: standard inputOutput file: standard outputJohn von Neumann, b. Dec. 28, 1903, d. Feb. 8, 1957, was aHungarian-American mathematician who made important contributions to the foundations of mathematics, logic, quantum physics, meteorology, science, computers, and game theory. He was noted for a phenomenal memory and thespeed with which he absorbed ideas and solved problems. In 1925 he receiveda B.S. diploma in chemical engineering from Zurich Institute and in 1926 aPh.D. in mathematics from the University of Budapest, His Ph.D.dissertation on set theory was an important contributions to the subject.At the age of 20, von Neumann proposed a new definition of ordinal numbersthat was universally adopted. While still in his twenties, he made many contributions in both pure and applied mathematics that established him asa mathematician of unusual depth. His Mathematical Foundation of Quantum Mechanics (1932) built a solid framework for the new scientific discipline.During this time he also proved the mini-max theorem of GAME THEORY. He gradually expanded his work in game theory, and with coauthor OskarMorgenstern he wrote Theory of Games and Economic Behavior (1944).There are some numbers which can be expressed by the sum of factorials. For example 9, 9 = 1! + 2! + 3! . Dr. von Neumann was very interested in such numbers. So, he gives you a number n, and wants you to tell whether or notthe number can be expressed by the sum of some factorials.Well, it is just a piece of case. For a given n, you will check if thereare some xi, and let n equal to∑t (上标) i=1（下标） xi! (t≥1, xi≥0, xi = xj <==> i = j)t即∑ xi! (t≥1, xi≥0, xi = xj <==> i = j)i=1If the answer is yes, say "YES"; otherwise, print out"NO".InputYou will get a non-negative integer n (n≤1,000,000) from input file.OutputFor the n in the input file, you should print exactly one word ("YES" or "NO") in a single line. No extra spaces are allowed.Sample input and outputStandard input standard output9 YES2 YESProblem D. Zero-complexity TranspositionInput file: standard inputOutput file: standard outputYou are given a sequence of integer numbers. Zero-complexity transpositionof the sequence is the reverse of this sequence. Your task is to write a program that prints zero-complexity transposition of the given sequence.InputThe first line of the input file contains one integer n-length of thesequence (0 ＜ n ≤10 000). The second line contains n integersnumbers-a1, a2, …, an (-1 000 000 000 000 000 ≤ ai ≤1 000 000 000 000 000).OutputOn the first line of the output file print the sequence in the reverseorder.Sample input and outputStandard input standard output3 3 2 11 2 35 9 -86 4 -3-3 4 6 -8 9。
