- 相關(guān)推薦
2016年計(jì)算機(jī)筆試考試題及答案
2016年計(jì)算機(jī)等級考試就要開始了，同學(xué)們復(fù)習(xí)好了嗎?下面yjbys小編為大家準(zhǔn)備的是關(guān)于網(wǎng)絡(luò)筆試的考試題及答案，希望能幫助大家順利通過考試!
【字符串】
1、輸入一個(gè)字符串，打印出該字符串中字符的所有排列。
例如輸入字符串a(chǎn)bc，則輸出由字符a、b、c所能排列出來的所有字符串a(chǎn)bc、acb、bac、bca、cab和cba。
2、有一個(gè)由大小寫組成的字符串，現(xiàn)在需要對他進(jìn)行修改，將其中的所有小寫字母排在大寫字母的前面
(大寫或小寫字母之間不要求保持原來次序)，如有可能盡量選擇時(shí)間和空間效率高的算法。
c語言函數(shù)原型void proc(char *str)，也可以采用你自己熟悉的語言。
3、編寫反轉(zhuǎn)字符串的程序，要求優(yōu)化速度、優(yōu)化空間。
4、用C語言實(shí)現(xiàn)函數(shù)void * memmove(void *dest, const void *src, size_t n)。
memmove函數(shù)的功能是拷貝src所指的內(nèi)存內(nèi)容前n個(gè)字節(jié)到dest所指的地址上。
分析：由于可以把任何類型的指針賦給void類型的指針，這個(gè)函數(shù)主要是實(shí)現(xiàn)各種數(shù)據(jù)類型的拷貝。
5、編程找出兩個(gè)字符串中最大公共子字符串,如"abccade", "dgcadde"的最大子串為"cad"。
6、輸入一個(gè)字符串，輸出該字符串中對稱的子字符串的最大長度。
比如輸入字符串"google"，由于該字符串里最長的對稱子字符串是"goog"，因此輸出4。
7、字符串原地壓縮。題目描述：“eeeeeaaaff" 壓縮為 "e5a3f2"，請編程實(shí)現(xiàn)。
8、請以回溯與不回溯算法實(shí)現(xiàn)字符串匹配。
9、輸入一個(gè)英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變。句子中單詞以空格符隔開。
為簡單起見，標(biāo)點(diǎn)符號和普通字母一樣處理。
例如：輸入"I am a student."，則輸出"student. a am I"。
10、在一個(gè)字符串中找到第一個(gè)只出現(xiàn)一次的字符。如輸入abaccdeff，則輸出b。
11、寫一個(gè)函數(shù)，它的原形是int continumax(char *outputstr,char *intputstr)
功能：
在字符串中找出連續(xù)最長的數(shù)字串，并把這個(gè)串的長度返回，并把這個(gè)最長數(shù)字串付給其中一個(gè)函數(shù)參數(shù)outputstr所指內(nèi)存。
例如："abcd12345ed125ss123456789"的首地址傳給intputstr后，函數(shù)將返回9，outputstr所指的值為123456789。
12、定義字符串的左旋轉(zhuǎn)操作：把字符串前面的若干個(gè)字符移動(dòng)到字符串的尾部。
如：把字符串a(chǎn)bcdef左旋轉(zhuǎn)2位得到字符串cdefab。請實(shí)現(xiàn)字符串左旋轉(zhuǎn)的函數(shù)。
要求時(shí)間對長度為n的字符串操作的復(fù)雜度為O(n)，輔助內(nèi)存為O(1)。
13、有n個(gè)長為m+1的字符串，如果某個(gè)字符串的最后m個(gè)字符與某個(gè)字符串的前m個(gè)字符匹配，則兩個(gè)字符串可以聯(lián)接。
問這n個(gè)字符串最多可以連成一個(gè)多長的字符串，如果出現(xiàn)循環(huán)，則返回錯(cuò)誤。
14、如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個(gè)字符串二中，則字符串一稱之為字符串二的子串。
注意，并不要求子串(字符串一)的字符必須連續(xù)出現(xiàn)在字符串二中。
請編寫一個(gè)函數(shù)，輸入兩個(gè)字符串，求它們的最長公共子串，并打印出最長公共子串。
例如：輸入兩個(gè)字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長公共子串，
則輸出它們的長度4，并打印任意一個(gè)子串。
分析：求最長公共子串(Longest Common Subsequence, LCS)是一道非常經(jīng)典的動(dòng)態(tài)規(guī)劃題。
15、輸入兩個(gè)字符串，從第一字符串中刪除第二個(gè)字符串中所有的字符。
例如，輸入"They are students."和"aeiou"，則刪除之后的第一個(gè)字符串變成"Thy r stdnts."。
16、一個(gè)文件，內(nèi)含一千萬行字符串，每個(gè)字符串在1K以內(nèi)，要求找出所有相反的串對，如abc和cba。
17、給出一個(gè)函數(shù)來復(fù)制兩個(gè)字符串A和B。字符串A的后幾個(gè)字節(jié)和字符串B的前幾個(gè)字節(jié)重疊。
18、已知一個(gè)字符串，比如asderwsde,尋找其中的一個(gè)子字符串比如sde的個(gè)數(shù)，如果沒有返回0，有的話返回子字符串的個(gè)數(shù)。
19、求最大連續(xù)遞增數(shù)字串(如"ads3sl456789DF3456ld345AA"中的"456789")。
20、實(shí)現(xiàn)strstr功能，即在父串中尋找子串首次出現(xiàn)的位置。
21、編碼完成下面的處理函數(shù)。
函數(shù)將字符串中的字符'*'移到串的前部分，前面的非'*'字符后移，但不能改變非'*'字符的先后順序，函數(shù)返回串中字符'*'的數(shù)量。
如原始串為：ab**cd**e*12，處理后為*****abcde12，函數(shù)并返回值為5。(要求使用盡量少的時(shí)間和輔助空間)
22、刪除字符串中的數(shù)字并壓縮字符串。如字符串”abc123de4fg56”處理后變?yōu)?rdquo;abcdefg”。注意空間和效率。
23、求兩個(gè)串中的第一個(gè)最長子串(神州數(shù)碼以前試題)。如"abractyeyt"，"dgdsaeactyey"的最大子串為"actyet"。
【棧、鏈表、樹、圖】
1、編寫一個(gè)程序，把一個(gè)有序整數(shù)數(shù)組放到二叉樹中。
2、編程實(shí)現(xiàn)從頂部開始逐層打印二叉樹節(jié)點(diǎn)數(shù)據(jù)。[參考]
3、編程實(shí)現(xiàn)單鏈表逆轉(zhuǎn)。
4、設(shè)計(jì)一個(gè)算法，找出二叉樹上任意兩個(gè)結(jié)點(diǎn)的最近共同父結(jié)點(diǎn)。復(fù)雜度不能為O(n2)。
5、二叉排序樹中，令f = (最大值+最小值) / 2，設(shè)計(jì)一個(gè)算法，找出距離f值最近、大于f值的結(jié)點(diǎn)。復(fù)雜度不能為O(n2)。
6、有雙向循環(huán)鏈表結(jié)點(diǎn)定義為：
struct node
{
int data;
struct node *front,*next;
};
有兩個(gè)雙向循環(huán)鏈表A，B，知道其頭指針為：pHeadA、pHeadB，請寫一函數(shù)將兩鏈表中data值相同的結(jié)點(diǎn)刪除。
更多相關(guān)文章推薦閱讀：
3.2016年計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)面試題及答案
6.2016年計(jì)算機(jī)等級考試二級VFP筆試試題及答案
9.2016年計(jì)算機(jī)一級MSOffice考試試題及答案
7、輸入一個(gè)鏈表的頭結(jié)點(diǎn)，從尾到頭反過來輸出每個(gè)結(jié)點(diǎn)的值。鏈表結(jié)點(diǎn)定義如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
8、輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。
要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只調(diào)整指針的指向。
10
/ \
6 14
/ \ / \
4 8 12 16
轉(zhuǎn)換成雙向鏈表
4=6=8=10=12=14=16。
首先我們定義的二元查找樹 節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
}; [參考]
9、設(shè)計(jì)包含min函數(shù)的棧。
定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個(gè)min函數(shù)，能夠得到棧的最小元素。
要求函數(shù)min、push以及pop的時(shí)間復(fù)雜度都是O(1)。
10、輸入一個(gè)整數(shù)和一棵二元樹。從樹的根結(jié)點(diǎn)開始往下訪問一直到葉結(jié)點(diǎn)所經(jīng)過的所有結(jié)點(diǎn)形成一條路徑。
打印出和與輸入整數(shù)相等的所有路徑。
例如 輸入整數(shù)22和如下二元樹
10
/ \
5 12
/ \
4 7
則打印出兩條路徑：10, 12和10, 5, 7。
二元樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義為：
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};
11、給出倆個(gè)單向鏈表的頭指針，比如h1，h2，判斷這倆個(gè)鏈表是否相交。為了簡化問題，我們假設(shè)倆個(gè)鏈表均不帶環(huán)。
問題擴(kuò)展：
(1) 如果鏈表可能有環(huán)列?
(2) 如果需要求出倆個(gè)鏈表相交的第一個(gè)節(jié)點(diǎn)列?
12、輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹的后序遍歷的結(jié)果。
如果是返回true，否則返回false。
例如輸入5、7、6、9、11、10、8，由于這一整數(shù)序列是如下樹的后序遍歷結(jié)果：
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果輸入7、4、6、5，沒有哪棵樹的后序遍歷的結(jié)果是這個(gè)序列，因此返回false。
13、如果我們把二叉樹看成一個(gè)圖，父子節(jié)點(diǎn)之間的連線看成是雙向的，我們姑且定義"距離"為兩節(jié)點(diǎn)之間邊的個(gè)數(shù)。
寫一個(gè)程序，求一棵二叉樹中相距最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)之間的距離。
14、輸入一個(gè)單向鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。鏈表的倒數(shù)第0個(gè)結(jié)點(diǎn)為鏈表的尾指針。
鏈表結(jié)點(diǎn)定義如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
15、輸入一顆二元查找樹，將該樹轉(zhuǎn)換為它的鏡像，即在轉(zhuǎn)換后的二元查找樹中，左子樹的結(jié)點(diǎn)都大于右子樹的結(jié)點(diǎn)。
用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。
例如輸入：
8
/ \
6 10
/\ /\
5 7 9 11
輸出：
8
/ \
10 6
/ \/ \
11 97 5
定義二元查找樹的結(jié)點(diǎn)為：
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
}; [參考]
16、求一個(gè)二叉樹中任意兩個(gè)節(jié)點(diǎn)間的最大距離，兩個(gè)節(jié)點(diǎn)的距離的定義是 這兩個(gè)節(jié)點(diǎn)間邊的個(gè)數(shù)。
比如某個(gè)孩子節(jié)點(diǎn)和父節(jié)點(diǎn)間的距離是1，和相鄰兄弟節(jié)點(diǎn)間的距離是2，優(yōu)化時(shí)間空間復(fù)雜度。
17、求一個(gè)有向連通圖的割點(diǎn)，割點(diǎn)的定義是，如果除去此節(jié)點(diǎn)和與其相關(guān)的邊，有向圖不再連通，描述算法。
18、設(shè)計(jì)一個(gè)棧結(jié)構(gòu)，滿足一下條件：min，push，pop操作的時(shí)間復(fù)雜度為O(1)。
19、請修改append函數(shù)，利用這個(gè)函數(shù)實(shí)現(xiàn)：
兩個(gè)非降序鏈表的并集，1->2->3 和 2->3->5 并為 1->2->3->5
另外只能輸出結(jié)果，不能修改兩個(gè)鏈表的數(shù)據(jù)。
20、遞歸和非遞歸倆種方法實(shí)現(xiàn)二叉樹的前序遍歷。
21、輸入一棵二元樹的根結(jié)點(diǎn)，求該樹的深度。
從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過的結(jié)點(diǎn)(含根、葉結(jié)點(diǎn))形成樹的一條路徑，最長路徑的長度為樹的深度。
22、用倆個(gè)棧實(shí)現(xiàn)隊(duì)列，某隊(duì)列的聲明如下：
template class CQueue
{
public:
CQueue() {}
~CQueue() {}
void appendTail(const T& node); // append a element to tail
void deleteHead(); // remove a element from head
private:
T m_stack1;
T m_stack2;
};
23、給定鏈表的頭指針和一個(gè)結(jié)點(diǎn)指針，在O(1)時(shí)間刪除該結(jié)點(diǎn)。鏈表結(jié)點(diǎn)的定義如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
函數(shù)的聲明如下：void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);
24、兩個(gè)單向鏈表，找出它們的第一個(gè)公共結(jié)點(diǎn)。
更多相關(guān)文章推薦閱讀：
3.2016年計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)面試題及答案
6.2016年計(jì)算機(jī)等級考試二級VFP筆試試題及答案
9.2016年計(jì)算機(jī)一級MSOffice考試試題及答案
鏈表的結(jié)點(diǎn)定義為：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
25、用遞歸顛倒一個(gè)棧。例如輸入棧{1, 2, 3, 4, 5}，1在棧頂。顛倒之后的棧為{5, 4, 3, 2, 1}，5處在棧頂。
26、二叉樹的結(jié)點(diǎn)定義如下：
struct TreeNode
{
int m_nvalue;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
輸入二叉樹中的兩個(gè)結(jié)點(diǎn)，輸出這兩個(gè)結(jié)點(diǎn)在數(shù)中最低的共同父結(jié)點(diǎn)。
27、有一個(gè)復(fù)雜鏈表，其結(jié)點(diǎn)除了有一個(gè)m_pNext指針指向下一個(gè)結(jié)點(diǎn)外，還有一個(gè)m_pSibling指向鏈表中的任一結(jié)點(diǎn)或者NULL。
其結(jié)點(diǎn)的C++定義如下：
struct ComplexNode
{
int m_nValue;
ComplexNode* m_pNext;
ComplexNode* m_pSibling;
};
下圖是一個(gè)含有5個(gè)結(jié)點(diǎn)的該類型復(fù)雜鏈表。
圖中實(shí)線箭頭表示m_pNext指針，虛線箭頭表示m_pSibling指針。為簡單起見，指向NULL的指針沒有畫出。
請完成函數(shù)ComplexNode* Clone(ComplexNode* pHead)，以復(fù)制一個(gè)復(fù)雜鏈表。
28、給定單鏈表、檢測是否有環(huán)。
29、給定兩個(gè)單鏈表(head1, head2)，檢測兩個(gè)鏈表是否有交點(diǎn)，如果有返回第一個(gè)交點(diǎn)。
30、給定單鏈表(head)，如果有環(huán)的話請返回從頭結(jié)點(diǎn)進(jìn)入環(huán)的第一個(gè)節(jié)點(diǎn)。
31、只給定單鏈表中某個(gè)結(jié)點(diǎn)p(并非最后一個(gè)結(jié)點(diǎn)，即p->next!=NULL)指針，刪除該結(jié)點(diǎn)。
32、只給定單鏈表中某個(gè)結(jié)點(diǎn)p(非空結(jié)點(diǎn))，在p前面插入一個(gè)結(jié)點(diǎn)。
33、編寫實(shí)現(xiàn)鏈表排序的一種算法。說明為什么你會(huì)選擇用這樣的方法?
34、編寫實(shí)現(xiàn)數(shù)組排序的一種算法。說明為什么你會(huì)選擇用這樣的方法?
35、怎樣編寫一個(gè)程序，把一個(gè)有序整數(shù)數(shù)組放到二叉樹中?
更多相關(guān)文章推薦閱讀：
3.2016年計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)面試題及答案
6.2016年計(jì)算機(jī)等級考試二級VFP筆試試題及答案
9.2016年計(jì)算機(jī)一級MSOffice考試試題及答案
【計(jì)算機(jī)筆試考試題及答案】相關(guān)文章：
臨床執(zhí)業(yè)醫(yī)師綜合筆試考試題及答案10-29
大學(xué)計(jì)算機(jī)基礎(chǔ)考試題及答案09-20
計(jì)算機(jī)基礎(chǔ)考試題庫及答案06-20
計(jì)算機(jī)考試題庫及答案01-13
職稱計(jì)算機(jī)考試題庫及答案07-12